Fast, effective vertex cover kernelization

Abu-Khzam, F.N.; Langston, M.A.; Suters, W.H.

Fast, effective vertex cover kernelization

Abu-Khzam, F.N.; Langston, M.A.; Suters, W.H.

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

URL: http://ieeexplore.ieee.org/abstract/document/1387015/

DOI: http://dx.doi.org/10.1006/bbrc.1994.188310.1109/AICCSA.2005.1387015

Date: 2017-03-20

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:

Summary form only given. Two kernelization methods for the vertex cover problem are investigated. The first, LP-kernelization has been in prior use and is known to produce predictable results. The second, crown reduction, is newer and faster but generates more variable results. Previously-unknown connections between these powerful methods are established. It is also shown that the problem of finding an induced crown-free subgraph in an arbitrary graph is decidable in polynomial time. Applications of crown structures are discussed.

Citation:

Abu-Khzam, F. N., Langston, M. A., & Suters, W. H. (2005). Fast, effective vertex cover kernelization: a tale of two algorithms. In Computer Systems and Applications, 2005. The 3rd ACS/IEEE International Conference on (p. 16). IEEE.