- LAUR Home
- →
- School of Arts and Sciences
- →
- SoAS - Scholarly Publications
- →
- View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
| 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.date.issued | 2018-04-26 | |
| 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 | en_US |
| 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 |
