The Optimal Design of Low-Latency Virtual Backbones

References

• Ahn N, Park S (2015) An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks. Wireless Networks 21(3):783–792.Crossref, Google Scholar
• Alon N, Moshkovitz D, Safra S (2006) Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms 2(2):153–177.Crossref, Google Scholar
• Baier G, Erlebach T, Hall A, Köhler E, Kolman P, Pangrác O, Schilling H, Skutella M (2010) Length-bounded cuts and flows. ACM Trans. Algorithms 7(1):679–690.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
• Buchanan A, Sung JS, Butenko S, Pasiliao EL (2015) An integer programming approach for fault-tolerant connected dominating sets. INFORMS J. Comput. 27(1):178–188.Link, Google Scholar
• Chen S, Ljubić I, Raghavan S (2010) The regenerator location problem. Networks 55(3):205–220.Crossref, Google Scholar
• Chen S, Ljubić I, Raghavan S (2015) The generalized regenerator location problem. INFORMS J. Comput. 27(2):204–220.Link, Google Scholar
• Dinur I, Steurer D (2014) Analytical approach to parallel repetition. Shmoys D, ed. Proc. 46th Annual ACM Sympos. Theory Comput. (ACM, New York), 624–633.Google Scholar
• Du D-Z, Wan P-J (2013) Connected Dominating Set: Theory and Applications, vol. 77 (Springer, New York).Google Scholar
• Edmonds J, Johnson EL (1970) Matching: a well-solved class of integer linear programs. Guy R, Hanani H, Sauer N, Schönheim, eds. Proc. Calgary Internat. Conf. Combin. Structures Their Appl (Gordon and Breach, Philadelphia), 89–92.Google Scholar
• Fan N, Watson J-P (2012) Solving the connected dominating set problem and power dominating set problem by integer programming. Lin G, ed. Combinatorial Optimization and Applications, vol. 7402 (Springer, New York), 371–383.Crossref, Google Scholar
• Feige U (1998) A threshold of ln  n for approximating set cover. J. ACM 45(4):634–652.Crossref, Google Scholar
• Fischetti M, Leitner M, Ljubić I, Luipersbeck M, Monaci M, Resch M, Salvagnin D, Sinnl M (2017) Thinning out Steiner trees: a node-based model for uniform edge costs. Math. Programming Comput. 9(2):203–229.Crossref, Google Scholar
• Fischetti M, Ljubić I, Sinnl M (2016) Redesigning Benders decomposition for large-scale facility location. Management Sci. 63(7):2146–2162.Link, Google Scholar
• Fujie T (2004) The maximum-leaf spanning tree problem: formulations and facets. Networks 43(4):212–223.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (WH Freeman and Company, New York).Google Scholar
• Gendron B, Lucena A, da Cunha AS, 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 (1993) Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2 (Springer, Berlin).Crossref, Google Scholar
• Haynes TW, Hedetniemi S, Slater P (1998) Fundamentals of Domination in Graphs (CRC Press, Clearwater, FL).Google Scholar
• Impagliazzo R, Paturi R (2001) On the complexity of k-SAT. J. Comput. System Sci. 62:367–375.Crossref, Google Scholar
• Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J. Comput. System Sci. 63:512–530.Crossref, Google Scholar
• Krishnamoorthy MS, Krishnamurthy B (1987) Fault diameter of interconnection networks. Comput. Math. Appl. 13(5):577–582.Crossref, Google Scholar
• Li D, Du H, Wan PJ, Gao X, Zhang Z, Wu W (2009) Construction of strongly connected dominating sets in asymmetric multihop wireless networks. Theoret. Comput. Sci. 410(8–10):661–669.Crossref, Google Scholar
• Li X, Aneja YP (2017) Regenerator location problem: Polyhedral study and effective branch-and-cut algorithms. Eur. J. Oper. Res. 257(1):25–40.Crossref, Google Scholar
• Li Y, Kim D, Zou F, Du D-Z (2008) Constructing minimum connected dominating sets with bounded diameters in wireless networks. IEEE Trans. Parallel Distributed Systems 20(2):147–157.Google Scholar
• Lovász L, Neumann-Lara V, Plummer M (1978) Mengerian theorems for paths of bounded length. Periodica Math. Hungarica 9(4):269–276.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
• Lund C, Yannakakis M (1994) On the hardness of approximating minimization problems. J. ACM 41(5):960–981.Crossref, Google Scholar
• Martin RK (1991) Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10(3):119–128.Crossref, Google Scholar
• Morgan MJ, Grout V (2008) Finding optimal solutions to backbone minimisation problems using mixed integer programming. Proc. 7th Internat. Network Conf. (Glyndŵr University Research Online), 53–64.Google Scholar
• Moshkovitz D (2015) The projection games conjecture and the NP-hardness of ln  n-approximating set-cover. Theory Comput. 11(7):221–235.Google Scholar
• Orlin JB (2013) Max flows in O(nm) time, or better. Boneh D, Roughgarden T, Feigenbaum J, eds. Proc. 45th Annual ACM Sympos. Theory Comput. (ACM, New York), 765–774.Google Scholar
• Raz R, Safra S (1997) A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. Raz R, Safra S, eds. Proc. 25th Annual ACM Sympos. Theory Comput. (ACM, New York), 475–484.Google Scholar
• Salemi H, Buchanan A (2019) Parsimonious formulations for low-diameter clusters. Accessed October 3, 2019, http://www.optimization-online.org/DB_HTML/2017/09/6196.html.Google Scholar
• Sassano A (1989) On the facial structure of the set covering polytope. Math. Program. 44(1–3):181–202.Crossref, Google Scholar
• Schaudt O (2013) On dominating sets whose induced subgraphs have a bounded diameter. Discrete Appl. Math. 161(16):2647–2652.Crossref, Google Scholar
• Schoone AA, Bodlaender HL, Van Leeuwen J (1987) Diameter increase caused by edge deletion. J. Graph Theory 11(3):409–427.Crossref, Google Scholar
• Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. Algorithms and Combinatorics, vol. 24 (Springer, Berlin).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. Pahl J, Reiners T, Voß S, eds. Internat. Conf. Network Optim. (Springer, Berlin), 162–169.Google Scholar
• Thorup M (2004) Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. Comput. System Sci. 69(3):330–353.Crossref, Google Scholar
• Veremyev A, Boginski V (2012) Identifying large robust network clusters via new compact formulations of maximum k-club problems. Eur. J. Oper. Res. 218(2):316–326.Crossref, Google Scholar
• Xie M, Haenggi M (2009) Toward an end-to-end delay analysis of wireless multihop networks. Ad Hoc Networks 7(5):849–861.Crossref, Google Scholar
• Xu J (2001) Topological Structure and Analysis of Interconnection Networks (Kluwer, Amsterdam).Crossref, Google Scholar
• Xu M, Xu JM, Hou XM (2005) Fault diameter of Cartesian product graphs. Inform. Processing Lett. 93(5):245–248.Crossref, Google Scholar
• Zhang N, Shin I, Zou F, Wu W, Thai MT (2008) Trade-off scheme for fault tolerant connected dominating sets on size and diameter. Proc. 1st ACM Internat. Workshop Foundations Wireless Ad Hoc Sensor Networking Comput. (ACM, New York), 1–8.Google Scholar
• Zhong Y, Haenggi M, Zheng FC, Zhang W, Quek TQ, Nie W (2017) Toward a tractable delay analysis in ultradense networks. IEEE Comm. Magazine 55(12):103–109.Google Scholar