Asymptotically faster algorithms for parameterized FACE COVER
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 pr...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , |
| التنسيق: | conferenceObject |
| منشور في: |
2005
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/7597 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://www.researchgate.net/publication/220789945_Asymptotically_Faster_Algorithms_for_Parameterized_FACE_COVER |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513482427203584 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Fernau, Henning Langston, Micheal A. |
| author2_role | author author |
| author_facet | Abu-Khzam, Faisal N. Fernau, Henning Langston, Micheal A. |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Fernau, Henning Langston, Micheal A. |
| dc.date.none.fl_str_mv | 2005 2018-04-26T08:45:50Z 2018-04-26T08:45:50Z 2018-04-26 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/7597 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). http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://www.researchgate.net/publication/220789945_Asymptotically_Faster_Algorithms_for_Parameterized_FACE_COVER |
| dc.language.none.fl_str_mv | en |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | Asymptotically faster algorithms for parameterized FACE COVER |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_59e92d6d3d9e5c2306d5b82eeec0a5db |
| identifier_str_mv | 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). |
| 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/7597 |
| publishDate | 2005 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Asymptotically faster algorithms for parameterized FACE COVERAbu-Khzam, Faisal N.Fernau, HenningLangston, Micheal A.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.N/A2018-04-26T08:45:50Z2018-04-26T08:45:50Z20052018-04-26Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObjecthttp://hdl.handle.net/10725/7597Abu-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).http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://www.researchgate.net/publication/220789945_Asymptotically_Faster_Algorithms_for_Parameterized_FACE_COVEReninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/75972021-03-19T10:43:13Z |
| spellingShingle | Asymptotically faster algorithms for parameterized FACE COVER Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | Asymptotically faster algorithms for parameterized FACE COVER |
| title_full | Asymptotically faster algorithms for parameterized FACE COVER |
| title_fullStr | Asymptotically faster algorithms for parameterized FACE COVER |
| title_full_unstemmed | Asymptotically faster algorithms for parameterized FACE COVER |
| title_short | Asymptotically faster algorithms for parameterized FACE COVER |
| title_sort | Asymptotically faster algorithms for parameterized FACE COVER |
| url | http://hdl.handle.net/10725/7597 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://www.researchgate.net/publication/220789945_Asymptotically_Faster_Algorithms_for_Parameterized_FACE_COVER |