Abstract
Given a connected, weighted, undirected graph G and a bound D, the bounded diameter minimum spanning tree problem seeks a spanning tree on G of minimum weight among the trees in which no path between two vertices contains more than D edges. In Prim's algorithm, the diameter of the growing spanning tree can always be known, so it is a good starting point from which to develop greedy heuristics for the bounded diameter problem. Abdalla, Deo, and Gupta described such an algorithm. It imitates Prim's algorithm but avoids edges whose inclusion in the spanning tree would violate the diameter bound. Running the algorithm from one start vertex requires time that is O(n3).
A modification of this approach uses the start vertex as the center of the spanning tree (if D is even) or as one of the two center vertices (if D is odd). This yields a simpler algorithm whose time is O(n2). A further modification chooses each next vertex at random rather than greedily, though it still connects each vertex to the growing tree with the lowest-weight feasible edge. On Euclidean problem instances with small diameter bounds, the randomized heuristic is superior to the two fully greedy algorithms, though its advantage fades as the diameter bound grows. On instances whose edge weights have been chosen at random, the fully greedy algorithms outperform the randomized heuristic.
- Abdalla, A., Deo, N., and Gupta, P. 2000. Random-tree diameter and the diameter constrained MST. Congressus Numerantium 144, 161--182.Google Scholar
- Achuthan, N. R., Caccetta, L., Caccetta, P., and Geelen, J. F. 1994. Computation methods for the diameter restricted minimum weight spanning tree problem. Australasian Journal of Combinatorics 10, 51--71.Google Scholar
- Althaus, E., Funke, S., Har-Peled, S., Könemann, J., Ramos, E. A., and Skutella, M. 2005. Approximating k-hop minimum-spanning trees. Operations Research Letters 33, 2, 115--120. Google ScholarDigital Library
- Beasley, J. E. 1990. OR-library: Distributing test problems by electronic mail. Journal of the Operational Research Society 41, 1069--1072.Google ScholarCross Ref
- Dahl, G. 1997. The 2-hop spanning tree problem. Tech. rep. 250, University of Oslo.Google Scholar
- Davis, L. 1991. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York.Google Scholar
- Deo, N. and Abdalla, A. 2000. Computing a diameter-constrained minimum spanning tree in parallel. In Algorithms and Complexity, G. Bongiovanni, G. Gambosi, and R. Petreschi, Eds. Number 1767 in LNCS. Springer-Verlag, Berlin, 17--31. Google ScholarDigital Library
- dos Santos, A. C., Lucena, A., and Rebeiro, C. C. 2004. Solving diameter constrained minimum spanning tree problems in dense graphs. In Experimental and Efficient Algorithms: Proceedings of the 3rd International Workshop, WEA 2004, C. C. Rebeiro and S. L. Martins, Eds. Number 3059 in LNCS. Springer, Berlin, 458--467.Google ScholarCross Ref
- Garey, M. R. and Johnson, D. S. 1979. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York. Google ScholarDigital Library
- Gouveia, L. and Magnanti, T. L. 2003. Network flow models for designing diameter-constrained minimum-spanning and Steiner trees. Networks 41, 159--173.Google ScholarCross Ref
- Gruber, M. and Raidl, G. R. 2005a. A new 0-1 ILP approach for the bounded diameter minimum spanning tree problem. In Proceedings of the 2nd International Network Optimization Conference. Vol. 1. 178--185. Lisbon.Google Scholar
- Gruber, M. and Raidl, G. R. 2005b. Variable neighborhood search for the bounded diameter minimum spanning tree problem. In Proceedings of the 18th Mini Euro Conference on Variable Neighborhood Search, P. Hansen, N. Mladenovic, J. A. M. Pérez, B. M. Batista, and J. M. Moreno-Vega, Eds. Tenerife, Spain.Google Scholar
- Gruber, M. and Raidl, G. R. 2008. Heuristic cut separation in a branch&cut approach for the bounded diameter minimum spanning tree problem. In Proceedings of the 2008 Symposium on Applications and the Internet. Turku, Finland. Google ScholarDigital Library
- Gruber, M., van Hemert, J., and Raidl, G. R. 2006. Neighborhood searches for the bounded diameter minimum spanning tree problem embedded in a VNS, EA, and ACO. In Proceedings of the 2006 Genetic and Evolutionary Computation Conference, M. Keijzer et al., Eds. Vol. 2. ACM Press, New York, 1187--1194. Google ScholarDigital Library
- Handler, G. Y. 1978. Minimax location of a facility in an undirected graph. Transportation Science 7, 287--293.Google ScholarDigital Library
- Julstrom, B. A. and Raidl, G. R. 2003. A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In 2003 Genetic and Evolutionary Computation Conference Workshop Program, A. Barry, Ed. 2--7. Chicago.Google Scholar
- King, R. S. and Julstrom, B. 1982. Applied Statistics Using the Computer. Alfred Publishing Company, Sherman Oaks, CA.Google Scholar
- Kopinitsch, B. 2006. An ant colony optimisation algorithm for the bounded diameter minimum spanning tree problem. M.S. thesis, Institute of Computer Graphics and Algorithms, Vienna University of Technology.Google Scholar
- Prim, R. C. 1957. Shortest connection networks and some generalizations. Bell System Technical Journal 36, 1389--1401.Google ScholarCross Ref
- Raidl, G. R. and Gruber, M. 2008. A Lagrangean relax-and-cut approach for the bounded diameter minimum spanning tree problem. In International Conference on Numerical Analysis and Applied Mathematics 2008. AIP Conference Proceedings, vol. 1048. American Institute of Physics, 446--449.Google Scholar
- Raidl, G. R. and Julstrom, B. A. 2003. Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In Proceedings of the 2003 ACM Symposium on Applied Computing, G. Lamont, H. Haddad, G. A. Papadopoulos, B. Panda, J. Carroll, R. Stansifer, W. Jones, R. Menezes, and W. Shoaff, Eds. ACM Press, New York, 747--752. Google ScholarDigital Library
- Singh, A. and Gupta, A. K. 2007. Improved heuristics for the bounded-diameter minimum spanning tree problem. Soft Computing 11, 10, 911--921. Google ScholarDigital Library
- Sörensen, K. and Janssens, G. K. 2002. Generating solutions for the 2-hop constrained spanning tree and the simple plant location problem in order of decreasing cost. In Proceedings of the 16th Belgian Conference on Quantitative Methods for Decision Making. Brussels.Google Scholar
Index Terms
- Greedy heuristics for the bounded diameter minimum spanning tree problem
Recommendations
A Heuristic for the Bounded Diameter Minimum Spanning Tree Problem
ISMSI '18: Proceedings of the 2nd International Conference on Intelligent Systems, Metaheuristics & Swarm IntelligenceGiven a connected, edge-weighted and undirected complete graph G(V,E,w), the bounded diameter minimum spanning tree (BDMST) problem deals with finding a spanning tree T of minimum cost in such a way that the diameter of T should not exceed D ≥ 2, where ...
Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem
SAC '03: Proceedings of the 2003 ACM symposium on Applied computingGiven a connected, weighted, undirected graph G and a bound D, the bounded-diameter minimum spanning tree problem seeks a spanning tree on G of lowest weight in which no path between two vertices contains more than D edges. This problem is NP-hard for 4 ...
New Heuristic Approaches for the Bounded-Diameter Minimum Spanning Tree Problem
<P>Given a bound, the bounded-diameter minimum spanning tree BDMST problem seeks a spanning tree of minimum total weight with a diameter not exceeding the given diameter bound. Depending on the tightness of the bound, optimal solutions have different ...
Comments