Crown reductions and decompositions [electronic resource] : theoretical results and practical methods /

by Suters, William Henry

Abstract (Summary)
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.
Bibliographical Information:


School:The University of Tennessee at Chattanooga

School Location:USA - Tennessee

Source Type:Master's Thesis



Date of Publication:

© 2009 All Rights Reserved.