A direct algorithm for the parameterized face cover problem

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Langston, Micheal A.
dc.date.accessioned 2017-03-21T12:55:16Z
dc.date.available 2017-03-21T12:55:16Z
dc.date.issued 2017-03-21
dc.identifier.uri http://hdl.handle.net/10725/5411
dc.description.abstract 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. en_US
dc.language.iso en en_US
dc.publisher Springer en_US
dc.title A direct algorithm for the parameterized face cover problem en_US
dc.type Conference Paper / Proceeding en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.conference.date September 14-17, 2004 en_US
dc.conference.pages 213-222 en_US
dc.conference.place Bergen, Norway en_US
dc.conference.title International Workshop on Parameterized and Exact Computation en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.author.affiliation Lebanese American University en_US
dc.title.volume Parameterized and Exact Computation en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account