TY - GEN
T1 - Computational study on dominating set problem of planar graphs
AU - Marzban, Marjan
AU - Gu, Qian-Ping
AU - Jia, Xiaohua
PY - 2008
Y1 - 2008
N2 - Recently, there has been significant theoretical progress towards fixed-parameter algorithms for the DOMINATING SET problem of planar graphs. It is known that the problem on a planar graph with n vertices and dominating number k can be solved in time using tree/branch-decomposition based algorithms, where c is some constant. However there has been no computational study report on the practical performances of the time algorithms. In this paper, we report computational results of Fomin and Thilikos algorithm which uses the branch-decomposition based approach. The computational results show that the algorithm can solve the DOMINATING SET problem of large planar graphs in a practical time for the class of graphs with small branchwidth. For the class of graphs with large branchwidth, the size of instances that can be solved by the algorithm in a practical time is limited to a few hundreds edges. The practical performances of the algorithm coincide with the theoretical analysis of the algorithm. The results of this paper suggest that the branch-decomposition based algorithms can be practical for some applications on planar graphs. © Springer-Verlag Berlin Heidelberg 2008.
AB - Recently, there has been significant theoretical progress towards fixed-parameter algorithms for the DOMINATING SET problem of planar graphs. It is known that the problem on a planar graph with n vertices and dominating number k can be solved in time using tree/branch-decomposition based algorithms, where c is some constant. However there has been no computational study report on the practical performances of the time algorithms. In this paper, we report computational results of Fomin and Thilikos algorithm which uses the branch-decomposition based approach. The computational results show that the algorithm can solve the DOMINATING SET problem of large planar graphs in a practical time for the class of graphs with small branchwidth. For the class of graphs with large branchwidth, the size of instances that can be solved by the algorithm in a practical time is limited to a few hundreds edges. The practical performances of the algorithm coincide with the theoretical analysis of the algorithm. The results of this paper suggest that the branch-decomposition based algorithms can be practical for some applications on planar graphs. © Springer-Verlag Berlin Heidelberg 2008.
KW - Branch-decomposition
KW - Computational study
KW - Data reduction
KW - Fixed-parameter algorithms
KW - PLANAR DOMINATING SET
UR - http://www.scopus.com/inward/record.url?scp=51849087637&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-51849087637&origin=recordpage
U2 - 10.1007/978-3-540-85097-7_9
DO - 10.1007/978-3-540-85097-7_9
M3 - 32_Refereed conference paper (with ISBN/ISSN)
SN - 3540850961
SN - 9783540850960
VL - 5165 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 89
EP - 102
BT - Combinatorial Optimization and Applications
PB - Springer Verlag
T2 - 2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008
Y2 - 21 August 2008 through 24 August 2008
ER -