Asymptotically faster algorithms for parameterized FACE COVER

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Fernau, Henning
dc.contributor.author Langston, Micheal A.
dc.date.accessioned 2018-04-26T08:45:50Z
dc.date.available 2018-04-26T08:45:50Z
dc.date.copyright 2005 en_US
dc.identifier.uri http://hdl.handle.net/10725/7597
dc.description.abstract The parameterized complexity of the face cover prob- lem is considered. The input to this problem is a plane graph, G, of order n. The question asked is whether, for any fixed k, there exists a set of k or fewer vertices whose boundaries collectively cover (contain) every vertex in G. The fastest previously-published face cover al- gorithm is achieved with the bounded search tree technique, in which branching requires O(5k + n2) time. In this paper, a structure the- orem of Aksionov et al. is combined with a detailed case analysis to produce a face cover algorithm that runs in O(4.5414k +n2) time. en_US
dc.language.iso en en_US
dc.title Asymptotically faster algorithms for parameterized FACE COVER en_US
dc.type Conference Paper / Proceeding en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.identifier.ctation Abu-Khzam, F. N., Fernau, H., & Langston, M. A. (2005). Asymptotically faster algorithms for the parameterized face cover problem. In Proceedings, International Workshop on Algorithms and Complexity in Durham (pp. 43-58). en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.conference.date 8-10 July 2005 en_US
dc.conference.pages 43-58
dc.conference.place Durham, UK en_US
dc.conference.title Algorithms and Complexity in Durham 2005 - Proceedings of the First ACiD Workshop en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url https://www.researchgate.net/publication/220789945_Asymptotically_Faster_Algorithms_for_Parameterized_FACE_COVER en_US
dc.orcid.id https://orcid.org/0000-0001-5221-8421 en_US
dc.author.affiliation Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account