Edge-packing by isomorphic subgraphs

Simple item page
dc.contributor.authorVergara, John Paul C.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2014-03-14T21:34:07Zen
dc.date.adate2009-04-18en
dc.date.available2014-03-14T21:34:07Zen
dc.date.issued1990en
dc.date.rdate2009-04-18en
dc.date.sdate2009-04-18en
dc.description.abstractMaximum 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.en
dc.description.degreeMaster of Scienceen
dc.format.extentviii, 75 leavesen
dc.format.mediumBTDen
dc.format.mimetypeapplication/pdfen
dc.identifier.otheretd-04182009-041312en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-04182009-041312/en
dc.identifier.urihttp://hdl.handle.net/10919/42147en
dc.language.isoenen
dc.publisherVirginia Techen
dc.relation.haspartLD5655.V855_1990.V478.pdfen
dc.relation.isformatofOCLC# 23657942en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.lccLD5655.V855 1990.V478en
dc.subject.lcshGraph theoryen
dc.titleEdge-packing by isomorphic subgraphsen
dc.typeThesisen
dc.type.dcmitypeTexten
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LD5655.V855_1990.V478.pdf
Size:
2.92 MB
Format:
Adobe Portable Document Format
Description:
Download

Collections

Masters Theses