Crown Structures for Vertex Cover Kernelization
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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | article |
| Published: |
2007
|
| Online Access: | http://hdl.handle.net/10725/2771 http://dx.doi.org/10.1007/s00224-007-1328-0 http://link.springer.com/article/10.1007/s00224-007-1328-0 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513459364823040 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Fellos, Micheal R. Langston, Micheal A. Suters, W. Henry |
| author2_role | author author author |
| author_facet | Abu-Khzam, Faisal N. Fellos, Micheal R. Langston, Micheal A. Suters, W. Henry |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Fellos, Micheal R. Langston, Micheal A. Suters, W. Henry |
| dc.date.none.fl_str_mv | 2007 2015-12-07T09:25:58Z 2015-12-07T09:25:58Z 2015-12-07 |
| dc.identifier.none.fl_str_mv | 1432-4350 http://hdl.handle.net/10725/2771 http://dx.doi.org/10.1007/s00224-007-1328-0 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. http://link.springer.com/article/10.1007/s00224-007-1328-0 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Theory of Computing Systems |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | Crown Structures for Vertex Cover Kernelization |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_545212459bb4b16ec4627bfb8f397e23 |
| identifier_str_mv | 1432-4350 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. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/2771 |
| publishDate | 2007 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Crown Structures for Vertex Cover KernelizationAbu-Khzam, Faisal N.Fellos, Micheal R.Langston, Micheal A.Suters, W. HenryCrown 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.PublishedN/A2015-12-07T09:25:58Z2015-12-07T09:25:58Z20072015-12-07Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article1432-4350http://hdl.handle.net/10725/2771http://dx.doi.org/10.1007/s00224-007-1328-0Abu-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.http://link.springer.com/article/10.1007/s00224-007-1328-0enTheory of Computing Systemsinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/27712016-08-08T08:19:54Z |
| spellingShingle | Crown Structures for Vertex Cover Kernelization Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | Crown Structures for Vertex Cover Kernelization |
| title_full | Crown Structures for Vertex Cover Kernelization |
| title_fullStr | Crown Structures for Vertex Cover Kernelization |
| title_full_unstemmed | Crown Structures for Vertex Cover Kernelization |
| title_short | Crown Structures for Vertex Cover Kernelization |
| title_sort | Crown Structures for Vertex Cover Kernelization |
| url | http://hdl.handle.net/10725/2771 http://dx.doi.org/10.1007/s00224-007-1328-0 http://link.springer.com/article/10.1007/s00224-007-1328-0 |