Edge-Packing in Planar Graphs

Simple item page
dc.contributor.authorHeath, Lenwood S.en
dc.contributor.authorVergara, John Paul C.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:37:18Zen
dc.date.available2013-06-19T14:37:18Zen
dc.date.issued1995-10-01en
dc.description.abstractMaximum 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 edge-packing for planar guests and planar hosts. Edge-packing is solvable in polynomial time when both G and H are either a 3-cycle or a k-star (graphs isomorphic to K(sub 1,k). Edge-packing is NP-complete when H is planar and G is either a cycle or a tree with greater than or equal to 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 1/2 optimal.en
dc.format.mimetypeapplication/postscripten
dc.identifierhttp://eprints.cs.vt.edu/archive/00000433/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000433/01/TR-95-18.psen
dc.identifier.trnumberTR-95-18en
dc.identifier.urihttp://hdl.handle.net/10919/19888en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleEdge-Packing in Planar Graphsen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Name:
TR-95-18.ps
Size:
396.75 KB
Format:
Postscript Files
Download

Collections

Computer Science Technical Reports