We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Edge-Packing in Planar Graphs.
- Authors
Heath, L. S.; Vergara, J. P. C.
- Abstract
Maximum G Edge-Packing (EPack[sub G]) is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graph G in a host graph H. This paper investigates the computational complexity of edgepacking for planar guests and planar hosts. Edge-packing is solvable in polynomial time when both G and H are trees. Edge-packing is solvable in linear time when H is outerplanar and G is either a 3-cycle or a k-star (a graph isomorphic to K[sub l,k]). Edge-packing is NP-complete when H is planar and G is either a cycle or a tree with ≥ 3 edges. A strategy for developing polynomial-time approximation algorithms for planar hosts is exemplified by a linear-time approximation algorithm that finds a k-star edge-packing of size at least half the optimal.
- Subjects
GRAPH theory; TREE graphs; ISOMORPHISM (Mathematics)
- Publication
Theory of Computing Systems, 1998, Vol 31, Issue 6, p629
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s002240000107