Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs |
| |
Authors: | Alber Bodlaender Fernau Kloks Niedermeier |
| |
Affiliation: | 1.Universit?t Tübingen, Wilhelm-Schickard-Institut für Informatik, Sand 13, D-72076 Tübingen, Germany. {alber,fernau,niedermr}@informatik.uni-tuebingen.de.,DE;2.Department of Computer Science, Utrecht University, Padualaan 14, De Uithof, NL-3584 CH Utrecht, The Netherlands. hansb@cs.uu.nl.,NL;3.ton@win.tue.nl.,NL |
| |
Abstract: | Abstract. We present an algorithm that constructively produces a solution to the k -DOMINATING SET problem for planar graphs in time O(c^ \sqrt k n) , where c=4^ 6\sqrt 34 . To obtain this result, we show that the treewidth of a planar graph with domination number γ (G) is O(\sqrt \rule 0pt 4pt \smash γ (G) ) , and that such a tree decomposition can be found in O(\sqrt \rule 0pt 4pt \smash γ (G) n) time. The same technique can be used to show that the k -FACE COVER problem (find a size k set of faces that cover all vertices of a given plane graph) can be solved in O(c
1
^ \sqrt k n) time, where c
1
=3^ 36\sqrt 34 and k is the size of the face cover set. Similar results can be obtained in the planar case for some variants of k -DOMINATING SET, e.g., k -INDEPENDENT DOMINATING SET and k -WEIGHTED DOMINATING SET. |
| |
Keywords: | , NP-complete problems, Fixed parameter tractability, Planar graphs, planar dominating set, face cover, Outerplanarity,,,,,,Treewidth, |
本文献已被 SpringerLink 等数据库收录! |
|