Fast, effective vertex cover kernelization
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 co...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , |
| التنسيق: | conferenceObject |
| منشور في: |
2017
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/5406 http://dx.doi.org/10.1006/bbrc.1994.188310.1109/AICCSA.2005.1387015 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://ieeexplore.ieee.org/abstract/document/1387015/ |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513476282548224 |
|---|---|
| author | Abu-Khzam, F.N. |
| author2 | Langston, M.A. Suters, W.H. |
| author2_role | author author |
| author_facet | Abu-Khzam, F.N. Langston, M.A. Suters, W.H. |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, F.N. Langston, M.A. Suters, W.H. |
| dc.date.none.fl_str_mv | 2017-03-20T10:35:40Z 2017-03-20T10:35:40Z 2017-03-20 |
| dc.identifier.none.fl_str_mv | 0-7803-8735-X http://hdl.handle.net/10725/5406 http://dx.doi.org/10.1006/bbrc.1994.188310.1109/AICCSA.2005.1387015 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. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://ieeexplore.ieee.org/abstract/document/1387015/ |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | IEEE |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | Fast, effective vertex cover kernelization a tale of two algorithms |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_82ade2eb2ed32aad22c8bf22bb30c0ed |
| identifier_str_mv | 0-7803-8735-X 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. |
| 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/5406 |
| publishDate | 2017 |
| publisher.none.fl_str_mv | IEEE |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Fast, effective vertex cover kernelizationa tale of two algorithmsAbu-Khzam, F.N.Langston, M.A.Suters, W.H.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.N/AIEEE2017-03-20T10:35:40Z2017-03-20T10:35:40Z2017-03-20Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObject0-7803-8735-Xhttp://hdl.handle.net/10725/5406http://dx.doi.org/10.1006/bbrc.1994.188310.1109/AICCSA.2005.1387015Abu-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.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttp://ieeexplore.ieee.org/abstract/document/1387015/eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/54062021-03-19T10:03:24Z |
| spellingShingle | Fast, effective vertex cover kernelization Abu-Khzam, F.N. |
| status_str | publishedVersion |
| title | Fast, effective vertex cover kernelization |
| title_full | Fast, effective vertex cover kernelization |
| title_fullStr | Fast, effective vertex cover kernelization |
| title_full_unstemmed | Fast, effective vertex cover kernelization |
| title_short | Fast, effective vertex cover kernelization |
| title_sort | Fast, effective vertex cover kernelization |
| url | http://hdl.handle.net/10725/5406 http://dx.doi.org/10.1006/bbrc.1994.188310.1109/AICCSA.2005.1387015 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://ieeexplore.ieee.org/abstract/document/1387015/ |