Crown Reductions and Decompositions: Theoretical Results and Practical Methods

Author

William Henry Suters, III, University of Tennessee - Knoxville

Date of Award

12-2004

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Michael A. Langston

Committee Members

Robert C. Ward, Bruce J. MacLennan

Abstract

Two kernelization schemes for the vertex cover problem, an NP-hard problem in graph theory, are compared. The first, crown reduction, is based on the identification of a graph structure called a crown and is relatively new while the second, LP-kernelization has been used for some time. A proof of the crown reduction algorithm is presented, the algorithm is implemented and theorems are proven concerning its performance. Experiments are conducted comparing the performance of crown reduction and LP- kernelization on real world biological graphs. Next, theorems are presented that provide a logical connection between the crown structure and LP-kernelization. Finally, an algorithm is developed for decomposing a graph into two subgraphs: one that is a crown and one that is crown free.

Recommended Citation

Suters, III, William Henry, "Crown Reductions and Decompositions: Theoretical Results and Practical Methods. " Master's Thesis, University of Tennessee, 2004.
https://trace.tennessee.edu/utk_gradthes/2225