×

zbMATH — the first resource for mathematics

New analysis and computational study for the planar connected dominating set problem. (English) Zbl 1354.90156
Summary: The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. F. Dorn et al. [Algorithmica 58, No. 3, 790–810 (2010; Zbl 1200.05223)] introduced a branch-decomposition based algorithm design technique for NP-hard problems in planar graphs and give an algorithm (DPBF algorithm) which solves the planar CDS problem in \(O(2^{9.822\sqrt n}n+n^3)\) time and \(O(2^{8.11\sqrt n}n+n^3)\) time, with a conventional method and fast matrix multiplication in the dynamic programming step of the algorithm, respectively. We show that DPBF algorithm solves the planar CDS problem in \(O(2^{9.8\sqrt n}n+n^3)\) time with a conventional method and in \(O(2^{8.08\sqrt n}n+n^3)\) time with a fast matrix multiplication. For a graph \(G\), let \(\mathrm{bw}(G)\) be the branchwidth of \(G\) and \(\gamma_c(G)\) be the connected dominating number of \(G\). We prove \(\mathrm{bw}(G)\leq 2\sqrt{10\gamma_c(G)}+32\). From this result, the planar CDS problem admits an \(O(2^{23.54\sqrt{\gamma_c(G)}}\gamma_c(G)+n^3)\) time fixed-parameter algorithm. We report computational study results on the practical performance of DPBF algorithm, which show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical analysis. For graphs with small or moderate branchwidth, the CDS problem instances with size up to a few thousands edges can be solved in a practical time and memory space.
MSC:
90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
Software:
LEDA; PIGALE; TSPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alber, J; Fellows, MR; Niedermeier, R, Polynomial time data reduction for dominating set, J ACM, 51, 363-384, (2004) · Zbl 1192.68337
[2] Alber, J; Dorn, F; Niedermeier, R, Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs, Discrete Appl Math, 145, 219-231, (2005) · Zbl 1084.05064
[3] Alber, J; Betzler, N; Niedermeier, R, Experiments on data reduction for optimal domination in networks, J Ann Oper Res, 146, 105-117, (2006) · Zbl 1106.90011
[4] Alber J, Dorn F, Niedermeier R Experiments on optimally solving NP-complete problems on planar graphs. Manuscript, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.4973&rep=rep1&type=pdf · Zbl 1084.05064
[5] Awick, U, All pairs shortest paths using bridging sets and rectangular matrix multiplication, J ACM, 49, 289-317, (2002) · Zbl 1326.05157
[6] Bian Z, Gu Q (2008) Computing branch decompositions of large planar graphs. In: Proceeding of the 7th International Workshop on Experimental Algorithms (WEA 2008). LNCS, vol 5038, pp. 87-100
[7] Bian Z, Gu Q, Marzban M, Tamaki H, Yoshitake Y (2008) Empirical study on branchwidth and branch decomposition of planar graphs. In: Proceedings of the 9th SIAM Workshop on Algorithm Engineering and Experiments (ALENEX’08), pp. 152-165 · Zbl 1244.05215
[8] Blum J, Ding M, Thaeler A, Cheng X (2005) Connected dominating set in sensor networks and MANETs. In: Du DZ, Pardalos P (eds) Handbooks of Combinatorial Optimization, (Supplementary vol B), Kluwer Academic Publishers, pp. 329-369 · Zbl 1117.90303
[9] Bodlaender HL, Cygan M, Kratsch S, Nederlof J (2013) Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In: Proceedings of the 2013 International Colloquium on Automata, Language and Programming (ICALP2013). LNCS, vol 7965, pp. 196-207 · Zbl 1296.68074
[10] Bodlaender HL, van Leeuwen EJ, van Rooij JMM, Vatshelle M (2010) Faster algorithms on branch and clique decompositions. In: Proceedings of the 2010 International Symposium on Mathematical Foundations of Computer Science (MFCS2010). LNCS, vol 6281, pp. 174-185 · Zbl 1287.05147
[11] Cheng, X; Ding, M; Du, H; Jia, X, Virtual backbone construction in multihop ad hoc wireless networks, Wirel Commun Mob Comput, 6, 183-190, (2006)
[12] Cygan M, Nederlof J, Pilipczuk Ma, Pilipczuk Mi, van Rooij JMM, Wojtaszczyk JO (2010) Solving connectivity problems parameterized by treewidth in single exponential time. In: Proceedings of the 2011 Annual Symposium on Foundations of Computer Science (FOCS2011), pp. 150-159 · Zbl 1292.68122
[13] Demaine ED, Hajiaghayi M (2005) Bidimensionality: new connections between FPT algorithms and PTAS. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 590-601 · Zbl 1297.05056
[14] Demaine, ED; Fomin, FV; Hajiaghayi, M; Thilikos, DM, Fixed parameter algorithms for (k, r)-center in planar graphs and map graphs, ACM Trans Algorithms, 1, 33-48, (2005) · Zbl 1321.05256
[15] Demaine, ED; Hajiaghayi, M, Bidimensionality theory and its algorithmic applications, Comput J, 51, 292-302, (2008)
[16] Dorn F (2006) Dynamic programming and fast matrix multiplication. In: Proceeding of the 14th Annual European Symposium on Algorithms (ESA2006). LNCS, vol 4168, pp. 280-291 · Zbl 1131.68484
[17] Dorn, F; Fomin, FV; Thilikos, DM, Subexponential parameterized algorithms, Comput Sci Rev, 2, 29-39, (2008) · Zbl 1302.68340
[18] Dorn, F; Penninkx, E; Bodlaender, HL; Fomin, FV, Efficient exact algorithms on planar graphs: exploiting sphere cut branch decompositions, Algorithmica, 58, 790-810, (2010) · Zbl 1200.05223
[19] Dorn, F; Fomin, FV; Thilikos, DM, Catalan structures and dynamic programming in h-minor-free graphs, J Comput Syst Sci, 78, 1606-1622, (2012) · Zbl 1244.05215
[20] Downey, RG; Fellows, MR, Fixed parameter tractability and completeness, Congr Numerantium, 87, 161-187, (1992) · Zbl 0768.68136
[21] Downey RG, Fellows MR (2013) Fundamentals of parameterized complexity. Texts in computer science. Springer, Berlin · Zbl 1358.68006
[22] Duchet, P; Meyniel, H, On hadwiger’s number and stability number, Ann Discrete Math, 13, 71-74, (1982) · Zbl 0522.05060
[23] Fafianie S, Bodlaender HL, Nederlof J (2013) Speeding up dynamic proramming with representative sets—an experimental evaluation of algorithms for Steiner tree on tree decompositions. In: Proceedings of the 2013 International Symposium on Parameterized and Exact Computation (IPEC2013). LNCS, vol 8246, pp. 321-334 · Zbl 1309.68209
[24] Fernau H, Juedes D (2004) A geometric approach to parameterized algorithms for domination problems on planar graphs. In: Proceedings of the 2004 International Symposium on Mathematical Foundations of Computer Science (MFCS2004). LNCS, vol 3153, pp. 488-499 · Zbl 1096.68167
[25] Fomin, FV; Thilikos, DM, Dominating sets in planar graphs: branch-width and exponential speed-up, SIAM J Comput, 36, 281-309, (2006) · Zbl 1114.05072
[26] Fomin, FV; Thilikos, DM, New upper bounds on the decomposability of planar graphs, J Graph Theory, 51, 53-81, (2006) · Zbl 1085.05049
[27] Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of NP-completeness. Freeman, New York · Zbl 0411.68039
[28] Gu, Q; Tamaki, H, Optimal branch-decomposition of planar graphs in \({O}(n^3)\) time, ACM Trans Algorithms, 4, 30:1-30:13, (2008) · Zbl 1445.68165
[29] Gu, Q; Tamaki, H, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \({O}(n^{1+ϵ })\) time, Theor Comput Sci, 412, 4100-4109, (2011) · Zbl 1217.68246
[30] Guha, S; Khuller, S, Approximation algorithms for connected dominating sets, Algorithmica, 20, 374-387, (1998) · Zbl 0895.68106
[31] Gu Q, Imani N (2010) Connectivity is not a limit for kernelization: planar connected dominating set. In: Proceeding of the 9th Latin American Theoretical Informatics Symposium (Latin 2010). LNCS, vol 6034, pp. 26-37 · Zbl 1283.05149
[32] Gu Q, Xu G (2014) Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs. In: Proceeding of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2014). LNCS, vol 8747, pp. 238-249 · Zbl 1417.05210
[33] Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998a) Domination in graphs. In: Monographs and textbooks in pure and applied mathematics, vol 209. Marcel Dekker, New York
[34] Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998b) Fundamentals of domination in graphs. In: Monographs and textbooks in pure and applied mathematics, vol 208. Marcel Dekker, New York
[35] Hicks, IV, Planar branch decompositions I: the ratcatcher, INFORMS J Comput, 17, 402-412, (2005) · Zbl 1239.05176
[36] Hicks, IV, Planar branch decompositions II: the cycle method, INFORMS J Comput, 17, 413-421, (2005) · Zbl 1239.05177
[37] Kammer F, Tholey T (2012) Approximate tree decompositions of planar graphs in linear time. In: Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2012), pp. 683-698 · Zbl 1348.68296
[38] Li, Xiang-Yang, Algorithmic, geometric and graphs issues in wireless networks, J Wirel Commun Mob Comput, 6, 119-140, (2003)
[39] Library of Efficient Data Types and Algorithms, Version 5.2 (2008). http://www.algorithmic-solutions.com/enleda.htm
[40] Liu H, Wan P, Yi C, Jia X, Makki S, Pissinou N (2005) Maximal lifetime scheduling in sensor surveillance networks. In: Proceeding of IEEE INFOCOM 2005 · Zbl 0799.05057
[41] Lokshtanov D, Mnich M, Saurabh S (2009) Linear kernel for planar connected dominating set. In: Proceeding of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009). LNCS, vol 5532, pp. 281-290 · Zbl 1241.68130
[42] Marzban, M; Gu, Q; Jia, X, Computational study on planar dominating set problem, Theor Comput Sci, 410, 5455-5466, (2009) · Zbl 1192.68488
[43] Marzban M, Gu Q, Jia X (2010) Computational study for planar connected dominating set problem. Proceeding of the 4th International Conference on Combinatorial Optimization and Applications (COCOA 2010). LNCS, vol 6509, pp. 107-116 · Zbl 1311.05194
[44] Public Implementation of a Graph Algorithm Library and Editor (2008). http://pigale.sourceforge.net/ · Zbl 1192.68337
[45] Reinelt, G, TSPLIB-A traveling salesman library, ORSA J Comput, 3, 376-384, (1991) · Zbl 0775.90293
[46] Robertson, N; Seymour, PD, Graph minors I. excluding a forest, J Comb Theory Ser B, 35, 39-61, (1983) · Zbl 0521.05062
[47] Robertson, N; Seymour, PD, Graph minors II. algorithmic aspects of tree-width, J Algorithms, 7, 309-322, (1986) · Zbl 0611.05017
[48] Robertson, N; Seymour, PD, Graph minors X. obstructions to tree decomposition, J Comb Theory Ser B, 52, 153-190, (1991) · Zbl 0764.05069
[49] Seymour, PD; Thomas, R, Call routing and the ratcatcher, Combinatorica, 14, 217-241, (1994) · Zbl 0799.05057
[50] The LEDA User Manual, Algorithmic Solutions, Version 4.2.1 (2008). http://www.mpi-inf.mpg.de/LEDA/MANUAL/MANUAL.html
[51] van Rooij JMM, Bodlaender HL, Rossmanith P (2009) Dynamic programming on tree decomposition using generalised fast subset convolution. In: Proceedings of the 2009 Annual European Symposium on Algorithms (ESA2009). LNCS, vol 5757, pp. 566-577 · Zbl 1256.68157
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.