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.
Citation:
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).
