An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets

References

• Ahn N, Park S (2014) An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks. Wireless Networks. Forthcoming.Google Scholar
• Blum J, Ding M, Thaeler A, Cheng X (2005) Connected dominating set in sensor networks and manets. Du D-Z, Pardalos PM, eds. Handbook of Combinatorial Optimization, Volume 5 (Springer, New York), 329–369.Crossref, Google Scholar
• Buchanan A, Sung JS, Boginski V, Butenko S (2014) On connected dominating sets of restricted diameter. Eur. J. Oper. Res. 236(2):410–418.Crossref, Google Scholar
• Butenko S, Cheng X, Oliveira C, Pardalos PM (2004) A new heuristic for the minimum connected dominating set problem on ad hoc wireless networks. Butenko S, Murphey R, Pardalos PM, eds. Recent Developments in Cooperative Control and Optimization, Volume 3 (Springer, New York), 61–73.Crossref, Google Scholar
• Chen S, Ljubić I, Raghavan S (2010) The regenerator location problem. Networks 55(3):205–220.Crossref, Google Scholar
• Cheng X, Huang X, Li D, Wu W, Du DZ (2003) A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 42(4):202–208.Crossref, Google Scholar
• Christof T, Löbel A, Stoer M (1997) PORTA-polyhedron representation transformation algorithm. Accessed January 10, 2015, http://www.iwr.uni-heidelberg.de/groups/comopt/software/PORTA/index.html.Google Scholar
• Dai F, Wu J (2006) On constructing k-connected k-dominating set in wireless ad hoc and sensor networks. J. Parallel Distributed Comput. 66(7):947–958.Crossref, Google Scholar
• do Forte V, Lucena A, Maculan N (2013) Formulations for the minimum 2-connected dominating set problem. Electronic Notes Discrete Math. 41:415–422.Crossref, Google Scholar
• Du DZ, Wan PJ (2013) Connected Dominating Set: Theory and Applications (Springer, New York).Crossref, Google Scholar
• Fan N, Watson JP (2012) Solving the connected dominating set problem and power dominating set problem by integer programming. Lin G, ed., Proc. 6th Internat. Conf., COCOA 2012, Banff, Alberta, Canada, 371–383.Crossref, Google Scholar
• Fomin FV, Grandoni F, Kratsch D (2008) Solving connected dominating set faster than 2n. Algorithmica 52(2):153–166.Crossref, Google Scholar
• Fujie T (2003) An exact algorithm for the maximum leaf spanning tree problem. Comput. Oper. Res. 30(13):1931–1944.Crossref, Google Scholar
• Fujie T (2004) The maximum-leaf spanning tree problem: Formulations and facets. Networks 43(4):212–223.Crossref, Google Scholar
• Füredi Z (1987) The number of maximal independent sets in connected graphs. J. Graph Theory 11(4):463–470.Crossref, Google Scholar
• Gabow HN (2006) Using expander graphs to find vertex connectivity. J. ACM 53(5):800–844.Crossref, Google Scholar
• Gendron B, Lucena A, Salles da Cunha A, Simonetti L (2014) Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem. INFORMS J. Comput. 26(4):645–657.Link, Google Scholar
• Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197.Crossref, Google Scholar
• Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20(4):374–387.Crossref, Google Scholar
• Gurobi Optimization, Inc. (2013) Gurobi Optimizer Reference Manual, http://www.gurobi.com.Google Scholar
• Gutwenger C, Mutzel P (2001) A linear time implementation of SPQR-trees. Marks J, ed., Proc. 8th Internat. Sympos., GD 2000, Colonial Williamsburg, VA, 77–90.Crossref, Google Scholar
• Henzinger MR, Rao S, Gabow HN (2000) Computing vertex connectivity: New bounds from old techniques. J. Algorithms 34(2):222–250.Crossref, Google Scholar
• Hopcroft JE, Tarjan RE (1973) Dividing a graph into triconnected components. SIAM J. Comput. 2(3):135–158.Crossref, Google Scholar
• Hunt HB, Marathe MV, Radhakrishnan V, Ravi SS, Rosenkrantz DJ, Stearns RE (1998) NC-approximation schemes for NP-and PSPACE-hard problems for geometric graphs. J. Algorithms 26(2):238–274.Crossref, Google Scholar
• Kanevsky A (1990) On the number of minimum size separating vertex sets in a graph and how to find all of them. Proc. First Ann. ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 411–421.Google Scholar
• Kanevsky A, Ramachandran V (1991) Improved algorithms for graph four-connectivity. J. Comput. System Sci. 42(3):288–306.Crossref, Google Scholar
• Khachian LG (1979) A polynomial algorithm in linear programming. Soviet Math. Doklady 20(1):191–194.Google Scholar
• Kloks T, Kratsch D (1998) Listing all minimal separators of a graph. SIAM J. Comput. 27(3):605–613.Crossref, Google Scholar
• Li Y, Wu Y, Ai C, Beyah R (2012) On the construction of k-connected m-dominating sets in wireless networks. J. Combinatorial Optim. 23(1):118–139.Crossref, Google Scholar
• Lichtenstein D (1982) Planar formulae and their uses. SIAM J. Comput. 11(2):329–343.Crossref, Google Scholar
• Lu HI, Ravi R (1998) Approximating maximum leaf spanning trees in almost linear time. J. Algorithms 29(1):132–141.Crossref, Google Scholar
• Lucena A, Maculan N, Simonetti L (2010) Reformulations and solution algorithms for the maximum leaf spanning tree problem. Comput. Management Sci. 7(3):289–311.Crossref, Google Scholar
• Matula DW (1978) k-blocks and ultrablocks in graphs. J. Combin. Theory, Ser. B 24(1):1–13.Crossref, Google Scholar
• Morgan M, Grout V (2008) Finding optimal solutions to backbone minimisation problems using mixed integer programming. Proc. 7th Internat. Network Conf. (INC 2008), Plymouth, UK, 53–64.Google Scholar
• Neumann A (2011) Implementation of Schmidts algorithm for certifying triconnectivity testing. Master’s thesis, Saarland University, Saarbrücken, Germany.Google Scholar
• Shang W, Wan P, Yao F, Hu X (2007) Algorithms for minimum m-connected k-tuple dominating set problem. Theoret. Comput. Sci. 381(1):241–247.Crossref, Google Scholar
• Simonetti L, da Cunha AS, Lucena A (2011) The minimum connected dominating set problem: Formulation, valid inequalities and a branch-and-cut algorithm. Network Optim., Lecture Notes in Computer Science, Volume 6701 (Springer, New York),162–169.Crossref, Google Scholar
• Tarjan RE (1972) Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2):146–160.Crossref, Google Scholar
• Thai MT, Zhang N, Tiwari R, Xu X (2007) On approximation algorithms of k-connected m-dominating sets in disk graphs. Theoret. Comput. Sci. 385(1–3):49–59.Crossref, Google Scholar
• Weisstein EW (2013) Perrin sequence. Math World—A Wolfram Web Resource. Accessed January 10, 2015, http://mathworld.wolfram.com/Perrin.Sequence.html.Google Scholar
• Wu Y, Li Y (2008) Construction algorithms for k-connected m-dominating sets in wireless sensor networks. Proc. 9th ACM Internat. Sympos. Mobile Ad Hoc Networking Comput., Hong Kong, 83–90.Crossref, Google Scholar
• Yuan D (2005) Energy-efficient broadcasting in wireless ad hoc networks: Performance benchmarking and distributed algorithms based on network connectivity characterization. Proc. 8th ACM Internat. Sympos. Modeling, Anal. Simulation Wireless Mobile Systems, Montreal, 28–35.Crossref, Google Scholar
• Zhang Z, Gao X, Wu W, Du D-Z (2009) A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks. J. Global Optim. 45(3):451–458.Crossref, Google Scholar
• Zhou J, Zhang Z, Wu W, Xing K (2014) A greedy algorithm for the fault-tolerant connected dominating set in a general graph. J. Combinatorial Optim. 28(1):310–319.Crossref, Google Scholar