EECS Publication
Asymptotically Faster Algorithms for the Parameterized face cover Problem
Faisal N. Abu-Khzam, Henning Fernau and Michael A. Langston
The parameterized complexity of the face cover problem 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 algorithm is achieved with the bounded search tree technique, in which branching requires O(5k + n^2) time. In this paper, a structure theorem of Aksionov et al. is combined with a detailed case analysis to produce a face cover algorithm that runs in O(4.5414k +n^2 ) time.
Published 2005-08-28 04:00:00 as ut-cs-05-564 (ID:166)