Edge-packing by isomorphic subgraphs
Vergara, John Paul C.
MetadataShow full item record
Maximum G Edge-Packing (E PackG) 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/|EG| optimal.
- Masters Theses