Computer Engineering & Science >
A Refined Algorithm for the Dominating Sets on Planar Graphs Based on Search Trees
Received date: 2010-07-26
Revised date: 2010-11-12
Online published: 2011-06-08
The dominating set in graphs is considered to be among the most important problems in combinatorial optimization, which is NPcomplete. From the viewpoint of FixedParameter Tractable, the problem is known to be W［2］complete for general graphs, which means that it is impossible to design an algorithms solve the problem with running time f(k)no(1).We investigate the version where we are given a planar graph G=(V ,E), a parameter k, and ask for a set of vertices of size at most k that dominate all other vertices. It is known to be fixedparameter tractable when restricted to a planar graph. We also give a search tree algorithm based on the two sets of reduction rules and the experiments to show the efficiency between different sets of reduction rules.
LAI Xinke,WU Xiaotian . A Refined Algorithm for the Dominating Sets on Planar Graphs Based on Search Trees[J]. Computer Engineering & Science, 2011 , 33(6) : 37 -40 . DOI: 10.3969/j.issn.1007130X.2011.
［1］Fellows M R, Langston M A. Nonconstructive Tools for Proving PolynomialTime Decidability［J］. Journal of the ACM , 1988, 35(3):727739.
［2］Fellows M R, Langston M A. On Search, Decision and the Efficiency of PolynomialTime Algorithms［J］. Journal of Computer and Systems Sciences, 1994,49(3):769779.
［3］GDowney R, Fellows M R. Parameterized Complexity［M］.Berlin:SpringerVerlag, 1999.
［4］Alber J, Fellows M R, Niedermeier R. PolynomialTime Data Reduction for Dominating Set［J］. Journal of the ACM, 2004,51(3):363384.
［5］Alber J, Fan H, Fellows M R, et al. A Refined Search Tree Technique for Dominating Set on Planar Graphs［J］. Journal of Computer and System Sciences,2005,71(4):385405.
［6］Mehlhorn K, Naher S, Uhrig C. LEDA: A Platform for Combinatorial and Geometric Computing［M］. Springer, 1999.
/
| 〈 |
|
〉 |