Edge-Packing by Isomorphic Subgraphs
| dc.contributor.author | Vergara, John Paul C. | en |
| dc.contributor.author | Heath, Lenwood S. | en |
| dc.contributor.department | Computer Science | en |
| dc.date.accessioned | 2013-06-19T14:36:19Z | en |
| dc.date.available | 2013-06-19T14:36:19Z | en |
| dc.date.issued | 1991 | en |
| dc.description.abstract | Maximum G Edge-Packing (EPackG) 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 edge-packing for planar guests and planar hosts. Edge-packing is solvable in linear time when G is a 2-path and H is arbitrary, or when H is outerplanar and G is either a 3-cycle or a k-star. Edge-packing is solvable in polynomial time when both G and H are trees. Edge-packing is NP-complete when H is planar and G is either a cycle or a tree with ≥3 edges. The approximability of EPackG is considered. A strategy for developing polynomial-time approximation algorithms for planar hosts is exemplified by a linear-time approximation algorithm for EPack k-star that finds an edge-packing of size at least one-half optimal. Finally, EPackG is shown not to be in the complexity class Max SNP, though it is Max SNP-hard for G a k-star, ≥3. | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier | http://eprints.cs.vt.edu/archive/00000250/ | en |
| dc.identifier.sourceurl | http://eprints.cs.vt.edu/archive/00000250/01/TR-91-03.pdf | en |
| dc.identifier.trnumber | TR-91-03 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/19668 | en |
| dc.language.iso | en | en |
| dc.publisher | Department of Computer Science, Virginia Polytechnic Institute & State University | en |
| dc.relation.ispartof | Historical Collection(Till Dec 2001) | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.title | Edge-Packing by Isomorphic Subgraphs | en |
| dc.type | Technical report | en |
| dc.type.dcmitype | Text | en |
Files
Original bundle
1 - 1 of 1