Abstract
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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science
- Level thesis:degree_level
- masters
- Discipline thesis:degree_discipline
- Computer Science
- Department dc:contributor.department
- Computer Science
- Grantor dc:publisher
- Virginia Tech
- Year dc:date.issued
- 1990
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Vergara, John Paul C.
Rights
dc:rights- Statement dc:rights
-
- In Copyright
- Licence dc:rights.uri
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Dc Identifier Other
- etd-04182009-041312
- OAI identifier oai:identifier
- oai:vtechworks.lib.vt.edu:10919/42147