Crown Structures for Vertex Cover Kernelization

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Fellos, Micheal R.
dc.contributor.author Langston, Micheal A.
dc.contributor.author Suters, W. Henry
dc.date.accessioned 2015-12-07T09:25:58Z
dc.date.available 2015-12-07T09:25:58Z
dc.date.copyright 2007
dc.date.issued 2015-12-07
dc.identifier.issn 1432-4350 en_US
dc.identifier.uri http://hdl.handle.net/10725/2771
dc.description.abstract Crown structures in a graph are defined and shown to be useful in kernelization algorithms for the classic vertex cover problem. Two vertex cover kernelization methods are discussed. One, based on linear programming, has been in prior use and is known to produce predictable results, although it was not previously associated with crowns. The second, based on crown structures, is newer and much faster, but produces somewhat variable results. These two methods are studied and compared both theoretically and experimentally with each other and with older, more primitive kernelization algorithms. Properties of crowns and methods for identifying them are discussed. Logical connections between linear programming and crown reductions are established. It is shown that the problem of finding an induced crown-free subgraph, and the problem of finding a crown of maximum size in an arbitrary graph, are solvable in polynomial time. en_US
dc.language.iso en en_US
dc.title Crown Structures for Vertex Cover Kernelization en_US
dc.type Article en_US
dc.description.version Published en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.woa N/A en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal Theory of Computing Systems en_US
dc.journal.volume 41 en_US
dc.journal.issue 3 en_US
dc.article.pages 411-430 en_US
dc.identifier.doi http://dx.doi.org/10.1007/s00224-007-1328-0 en_US
dc.identifier.ctation Abu-Khzam, F. N., Fellows, M. R., Langston, M. A., & Suters, W. H. (2007). Crown structures for vertex cover kernelization. Theory of Computing Systems, 41(3), 411-430. en_US
dc.author.email faisal.abukhzam@lau.edu.lb
dc.identifier.url http://link.springer.com/article/10.1007/s00224-007-1328-0

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account