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.

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.

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

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

Date: 2017-03-21

Terms of Use: This item is made available under the terms and conditions applicable to " Conference Paper / Proceeding ", as set forth at: http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php

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.