A direct algorithm for the parameterized face cover problem
With respect to a given plane graph, G, a face cover is defined as a set of faces whose boundaries collectively contain every vertex in G. It is known that, when k is fixed, finding a cover of size k (if indeed any exist) can be accomplished in polynomial time. Recent improvements to face cover algo...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | conferenceObject |
| Published: |
2017
|
| Online Access: | http://hdl.handle.net/10725/5411 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | With respect to a given plane graph, G, a face cover is defined as a set of faces whose boundaries collectively contain every vertex in G. It is known that, when k is fixed, finding a cover of size k (if indeed any exist) can be accomplished in polynomial time. Recent improvements to face cover algorithms are based on the theory of fixed-parameter tractability and reductions to planar dominating set. A major goal has been to reduce the time required for branching, which is the most computationally-intensive aspect of fixed-parameter tractable methods. The fastest previously-known method for solving planar dominating set requires branching time O(8kn). The main contribution of this paper is a direct and relatively simple O(5kn) face cover branching algorithm. A direct O(n2) face cover kernelization algorithm is also presented. |
|---|