Home
Resource
A general class of heuristics for constrained forest and cycle problems
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(16.64 MB)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Imielinska, Celina Z.. A general class of heuristics for constrained forest and cycle problems. Retrieved from https://doi.org/doi:10.7282/T3Z3221V

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleA general class of heuristics for constrained forest and cycle problems
NameImielinska, Celina Z. (author); Kalantari, Bahman (internal member); Souvaine, Diane (internal member); Steiger, Bill (internal member); Suri, Subhash (internal member); Rutgers University; Graduate School - New Brunswick
Date Created1993
Other Date1993-10 (degree)
SubjectComputer Science, Heuristic algorithms, Traveling-salesman problem, Algorithms
Extent1 online resource (xi, 139 p. : ill.)
DescriptionLet 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.
NoteIncludes bibliographical references
Noteby Celina Z. Imielinska
NotePh.D.
NoteIncludes vita
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3Z3221V
LanguageEnglish
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
Version 8.5.5
Rutgers University Libraries - Copyright ©2024