Text

theses

Includes bibliographical references

by Celina Z. Imielinska

Ph.D.

Includes vita

Let G = (V, E) be a connected, undirected, edge-weighted graph. A subgraph of G satisfying a certain criteria will be called an optimal solution if its total edge-weight is minimum among all subgraphs satisfying the given criteria. The minimum spanning tree (MST) of G is its optimal spanning tree. The constrained forest problem (CFP), a more general version of the MST/is the problem of finding an optimal spanning forest in which each tree spans at least m, a given number of vertices. When n = |Vj is a multiple of m, a variation of the CFP is the exact constrained forest problem (ECFP), where each tree spans exactly m vertices. We shall also refer to ECFP as the m-subtree problem. For m = 2, the m-subtree problem reduces to the minimum weight perfect matching problem which is the problem of finding an optimal set of edges such that each vertex is incident to exactly one edge. The traveling salesman problem (TSP) is the problem of finding an optimal tour (Hamiltonian cycle) covering all the vertices in V. A more general version of the TSP is the constrained cycle problem (CCP), which is the problem of finding an optimal set of vert ex-disjoint cycles each covering at least m vertices. For m — 3 the CCP reduces to the so-called 2-matching problem and for m = 4 to the triangle-free 2-matching problem. When n is a multiple of m, a variation of the CCP is the exact constrained cycle problem (ECCP) where each cycle covers exactly m vertices. We shall also refer to the ECCP as the m-perfect matching problem. Except for the boundary cases of the above mentioned problems e.g. MST, the perfect matching problem, these problems are NP-hard. A crucial component of the thesis is a fast 2-approximate heuristic for the CFP which is proved to be iVP-hard for m < 3. From this heuristic, under the assumption of the triangle inequality, we obtain a 4-approximate heuristic for the CCP and a general class of heuristics for the ECFP and the ECCP. In addition to the heuristic for the CFP, this general class of heuristics is a powerful combination of the Onethird and the hypergreedy heuristics for perfect matching. This class of heuristics allows adjustable time complexity and is capable of producing approximate solutions within either a constant or a very slowly growing function of n times the optimal weight.

doi:10.7282/T3Z3221V

ETD doctoral