Spelling suggestions: "subject:"ld5655.v855 1990.478"" "subject:"ld5655.v855 1990.1478""
1 |
Edge-packing by isomorphic subgraphsVergara, John Paul C. 18 April 2009 (has links)
Maximum G Edge-Packing (E Pack<sub>G</sub>) is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graph G in a host graph H. The problem is primarily considered for several guest graphs (stars, paths and cycles) and host graphs (arbitrary graphs, planar graphs and trees). We give polynomial-time algorithms when G is a 2-path or when H is a tree; we show the problem is NP-complete otherwise. Also, we propose straightforward greedy polynomial-time approximation algorithms which are at least 1/|E<sub>G</sub>| optimal. / Master of Science
|
Page generated in 0.0472 seconds