Vergara, John Paul C.2014-03-142014-03-141990etd-04182009-041312http://hdl.handle.net/10919/42147Maximum G Edge-Packing (E Pack_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. 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_G| optimal.viii, 75 leavesBTDapplication/pdfenIn CopyrightLD5655.V855 1990.V478Graph theoryThesishttp://scholar.lib.vt.edu/theses/available/etd-04182009-041312/