New Valid Inequalities for the Optimal Communication Spanning Tree Problem

References

• Agarwal YK (2013) Design of survivable networks using three-and four-partition facets. Oper. Res. 61(1):199–213.Link, Google Scholar
• Agarwal YK, Sharma P (2009) A Benders’ partitioning approach for solving the optimal communication spanning tree problem. Neogy SK, Das AK, Bapat RB, eds. Statistical Science and Interdisciplinary Research: Modeling, Computation, and Optimization (World Scientific Publishing, Singapore), 237–256.Google Scholar
• Ahuja RK, Murty VVS (1987) Exact and heuristic algorithms for the optimum communication spanning tree problem. Transportation Sci. 21(3):163–170.Link, Google Scholar
• Bienstock D, Chopra S, Günlük O, Tsai CY (1998) Minimum cost capacity installation for multicommodity network flows. Math. Program. 81(2):177–199.Crossref, Google Scholar
• Blin L, Potop-Butucaru MG, Rovedakis S (2011) Self-stabilizing minimum degree spanning tree within one from the optimal degree. J. Parallel Distributed Comput. 71(3):438–449.Crossref, Google Scholar
• Chopra S (1989) On the spanning tree polyhedron. Oper. Res. Lett. 8(1):25–29.Crossref, Google Scholar
• Chu HM, Chen CT, Wang PC (2017) Uninterrupted ethernet using failure-adaptive spanning trees. Internat. J. Comm. Systems 30(14):e3291.Crossref, Google Scholar
• Contreras I, Fernández E (2012) General network design: A unified view of combined location and network design problems. Eur. J. Oper. Res. 219(3):680–697.Crossref, Google Scholar
• Contreras I, Fernández E, Marín A (2009) Tight bounds from a path based formulation for the tree of hub location problem. Comput. Oper. Res. 36(12):3117–3127.Crossref, Google Scholar
• Contreras I, Fernández E, Marín A (2010a) Lagrangean bounds for the optimum communication spanning tree problem. TOP 18(1):140–157.Crossref, Google Scholar
• Contreras I, Fernández E, Marín A (2010b) The tree of hubs location problem. Eur. J. Oper. Res. 202(2):390–400.Crossref, Google Scholar
• D’Andreagiovanni F, Mett F, Nardin A, Pulaj J (2017) Integrating LP-guided variable fixing with MIP heuristics in the robust design of hybrid wired-wireless FTTx access networks. Appl. Soft Comput. 61(December):1074–1087.Crossref, Google Scholar
• Du D, Hu X (2008) Steiner Tree Problems in Computer Communication Networks (World Scientific Publishing, Singapore).Crossref, Google Scholar
• Fernández E, Luna-Mota C, Hildenbrandt A, Reinelt G, Wiesberg S (2013) A flow formulation for the optimum communication spanning tree. Electronic Notes Discrete Math. 41(June):85–92.Crossref, Google Scholar
• Fischetti M, Lancia G, Serafini P (2002) Exact algorithms for minimum routing cost trees. Networks 39(3):161–173.Crossref, Google Scholar
• Gollowitzer S, Gouveia L, Ljubić I (2011) The two level network design problem with secondary hop constraints. Network Optimization (Springer, Berlin, Heidelberg), 71–76.Crossref, Google Scholar
• Hu TC (1974) Optimum communication spanning trees. SIAM J. Comput. 3(3):188–195.Crossref, Google Scholar
• Huang N-F, Cheng Y-C (1992) An effective spanning tree algorithm for a bridged LAN. Proc. Internat. Workshop Advanced Comm. Appl. High Speed Networks (IEEE, New York), 43–49.Google Scholar
• Johnson DS, Lenstra JK, Kan AHG (1978) The complexity of the network design problem. Networks 8(4):279–285.Crossref, Google Scholar
• Li G, Balakrishnan A (2016) Models and algorithms for network reduction. Eur. J. Oper. Res. 248(3):930–942.Crossref, Google Scholar
• Luna-Mota C (2016) The optimum communication spanning tree problem-properties, models and algorithms. Unpublished PhD dissertation, Universitat Politécnica De Catalunya Barcelonatech, Barcelona, Spain.Google Scholar
• Magnanti TL, Wong RT (1984) Network design and transportation planning: Models and algorithms. Transportation Sci. 18(1):1–55.Link, Google Scholar
• Papadimitriou C, Yannakakis M (1991) Optimization, approximation, and complexity classes. J. Computer System Sci. 43(3):425–440.Crossref, Google Scholar
• Peleg D, Reshef E (1998) Deterministic polylog approximation for minimum communication spanning trees. Proc. International Colloquium on Automata, Languages, and Programming (Springer, Berlin), 670–681.Crossref, Google Scholar
• Rothlauf F (2009) On optimal solutions for the optimal communication spanning tree problem. Oper. Res. 57(2):413–425.Link, Google Scholar
• Sharma P (2006) Algorithms for the optimum communication spanning tree problem. Ann. Oper. Res. 143(1):203–209.Crossref, Google Scholar
• Soak SM (2006) A new evolutionary approach for the optimal communication spanning tree problem. IEICE Trans. Fundamentals Electronic Commun. Comput. Sci. 89(10):2882–2893.Crossref, Google Scholar
• Sommer J (2010) On optimal communication spanning trees in embedded Ethernet networks. Proc. 8th IEEE Internat. Workshop Factory Comm. Systems (IEEE, New York), 141–150.Crossref, Google Scholar
• Tilk C, Irnich S (2016) Combined column-and-row-generation for the optimal communication spanning tree problem. Technical Report LM-2016-03, Chair of Logistics Management, Johannes Gutenberg University Mainz, Mainz, Germany.Google Scholar
• Wieselthier JE, Nguyen GD, Ephremides A (2000) On the construction of energy-efficient broadcast and multicast trees in wireless networks. Proc. IEEE INFOCOM 2000 19th Ann. Joint Conf. IEEE Comput. Comm. Soc. vol. 2. (IEEE, New York), 585–594.Crossref, Google Scholar
• Wu BY (2002) A polynomial time approximation scheme for the two-source minimum routing cost spanning trees. J. Algorithms 44(2):359–378.Crossref, Google Scholar
• Wu BY, Chao KM, Tang CY (2000a) Approximation algorithms for some optimum communication spanning tree problems. Discrete Appl. Math. 102(3):245–266.Crossref, Google Scholar
• Wu BY, Chao KM, Tang CY (2000b) A polynomial time approximation scheme for optimal product-requirement communication spanning trees. J. Algorithms 36(2):182–204.Crossref, Google Scholar
• Wu BY, Lancia G, Bafna V, Chao KM, Ravi R, Tang CY (2000c) A polynomial time approximation scheme for minimum routing cost spanning trees. SIAM J. Comput. 29(3):761–788.Crossref, Google Scholar