ALENEX/ANALCO 2004

Abu-Khzam, Faisal N.; Collins, Rebecca L.; Fellows, Micheal R.; Langston, Micheal A.; Suters, W. Henry; Symons, Christopher T.

ALENEX/ANALCO 2004

Title: ALENEX/ANALCO 2004;
Kernelization algorithms for the vertex cover problem

Abu-Khzam, Faisal N.; Collins, Rebecca L.; Fellows, Micheal R.; Langston, Micheal A.; Suters, W. Henry; Symons, Christopher T.; SAS; 200302941; Computer Science and Mathematics; faisal.abukhzam@lau.edu.lb; Lebanese American University

URI: http://hdl.handle.net/10725/5409

URL: http://www.siam.org/meetings/alenex04/abstacts/F-Abu-Khzam.pdf

Abstract:

A variety of efficient kernelization strategies for the classic vertex cover problem are developed, implemented and compared experimentally. A new technique, termed crown reduction, is introduced and analyzed. Applications to computational biology are discussed.

Citation:

Abu-Khzam, F. N., Collins, R. L., Fellows, M. R., Langston, M. A., Suters, W. H., & Symons, C. T. (2004). Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments. ALENEX/ANALC, 69.