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 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| الملخص: | 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. |
|---|