New Heuristic Approaches for the Bounded-Diameter Minimum Spanning Tree Problem

References

• Abdalla A, Deo N (2002) Random-tree diameter and the diameter-constrained MST. Internat. J. Comput. Math. 79(6):651–663.Crossref, Google Scholar
• Achuthan NR, Caccetta L, Caccetta P, Geelen JF (1994) Computation methods for the diameter restricted minimum weight spanning tree problem. Australasian J. Combinatorics 10:51–71.Google Scholar
• Beasley JE (1990) OR-Library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072.Crossref, Google Scholar
• Binh HTT, McKay RI, Hoai NX, Nghia ND (2009) New heuristic and hybrid genetic algorithm for solving the bounded diameter minimum spanning tree problem. Proc. 11th Annual Conf. Genetic and Evolutionary Comput., GECCO 09 (ACM, Montreal), 373–380.Crossref, Google Scholar
• Dahl G, Flatberg T, Foldnes N, Gouveia L (2005) Hop-constrained spanning trees: The jump formulation and a relax-and-cut method. Technical report, University of Oslo, Centre of Mathematics for Applications, Oslo, Norway.Google Scholar
• Deo N, Abdalla A (2000) Computing a diameter-constrained minimum spanning tree in parallel. Bongiovanni G, Petreschi R, Gambosi G, eds. Algorithms and Complexity, Lecture Notes in Computer Science, Vol. 1767 (Springer, Berlin), 17–31.Crossref, Google Scholar
• dos Santos AC, Lucena A, Ribeiro C (2004) Solving diameter constrained minimum spanning tree problems in dense graphs. Ribeiro C, Martins S, eds. Experimental and Efficient Algorithms, Lecture Notes in Computer Science, Vol. 3059 (Springer, Berlin), 458–467.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York).Google Scholar
• Gouveia L, Magnanti TL (2003) Network flow models for designing diameter-constrained minimum-spanning and Steiner trees. Networks 41(3):159–173.Crossref, Google Scholar
• Gouveia L, Simonetti L, Uchoa E (2011) Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs. Math. Programming 128(1–2):123–148.Crossref, Google Scholar
• Gruber M, Raidl GR (2005) A new 0-1 ILP approach for the bounded diameter minimum spanning tree problem. Proc. 2nd Internat. Network Optim. Conf., Lisbon, Portugal, 178–185.Google Scholar
• Gruber M, Raidl GR (2009) Exploiting hierarchical clustering for finding bounded diameter minimum spanning trees on Euclidean instances. Proc. 11th Annual Conf. Genetic and Evolutionary Comput., GECCO’09 (ACM, Montreal), 263–270.Crossref, Google Scholar
• Gruber M, Raidl GR (2010) (Meta-)heuristic separation of jump cuts in a branch&cut approach for the bounded diameter minimum spanning tree problem. Maniezzo V, Stuetzle T, Voss S, Sharda R, eds. Matheuristics, Annals of Information Systems, Vol. 10 (Springer, New York), 209–229.Google Scholar
• Gruber M, van Hemert J, Raidl GR (2006) Neighbourhood searches for the bounded diameter minimum spanning tree problem embedded in a VNS, EA, and ACO. Proc. 8th Annual Conf. Genetic Evolutionary Comput., GECCO’06 (ACM, Seattle), 1187–1194.Crossref, Google Scholar
• Handler GY (1973) Minimax location of a facility in an undirected tree graph. Transportation Sci. 7(3):287–293.Link, Google Scholar
• Julstrom BA (2009) Greed heuristics for the bounded diameter minimum spanning tree problem. J. Experiment. Algorithmics (JEA) 14(1):111–1114.Google Scholar
• Kortsarz G, Peleg D (1999) Approximating the weight of shallow steiner trees. Discrete Appl. Math. 93(2–3):265–285.Crossref, Google Scholar
• Lucena A, Ribeiro C, Santos AC (2010) A hybrid heuristic for the diameter constrained minimum spanning tree problem. J. Global Optim. 46(3):363–381.Crossref, Google Scholar
• Prim RC (1957) Shortest connection networks and some generalizations. The Bell System Technical J. 36(6):1389–1401.Crossref, Google Scholar
• Raidl GR, Gruber M (2008) A Lagrangian relax-and-cut approach for the bounded diameter minimum spanning tree problem. AIP Conf. Proc. 1048(1):446–449.Crossref, Google Scholar
• Raidl GR, Julstrom BA (2003) Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem. SAC’03: Proc. 2003 ACM Sympos. Appl. Comput. (ACM, New York), 747–752.Crossref, Google Scholar
• Requejo C, Santos E (2009) Greedy heuristics for the diameter-constrained minimum spanning tree problem. J. Math. Sci. 161(6):930–943.Crossref, Google Scholar
• Singh A, Gupta AK (2007) Improved heuristics for the bounded-diameter minimum spanning tree problem. Soft Comput.—A Fusion of Foundations, Methodologies Appl. 11(10):911–921.Google Scholar