Title :
Parameterized VERTEX COVER in Graphs of Small Degree
Author_Institution :
Sch. of Comput. Sci., Carleton Univ., Ottawa, ON, Canada
fDate :
March 31 2009-April 2 2009
Abstract :
We describe a new approach to improve algorithms for solving the k-VERTEX COVER problem, that complements the state-of-the-art kernelization techniques based on solving maximum-flow instances. Our algorithm applies to graphs of small bounded degree, adapts existing k-vertex cover machinery, and incurs no additional complexity. We also investigate the applicability of our new algorithm to solving the Maximum Independent Set problem in graphs of small bounded degree.
Keywords :
graph theory; set theory; graph theory; k-vertex cover problem; kernelization technique; maximum independent set problem; maximum-flow instance; Bipartite graph; Computer science; Kernel; Machinery; Particle separators; Polynomials; Search methods; Tree graphs; Virtual colonoscopy; Algorithms; graph theory; parameterized complexity;
Conference_Titel :
Computer Science and Information Engineering, 2009 WRI World Congress on
Conference_Location :
Los Angeles, CA
Print_ISBN :
978-0-7695-3507-4
DOI :
10.1109/CSIE.2009.965
