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 lowest weight in which no path between two vertices contains more than D edges. This problem is NP-hard for 4 < D < n - 1, where n is the number of vertices in G. An existing greedy heuristic for the problem, called OTTC, is based on Prim's algorithm. OTTC usually yields poor results on instances in which the triangle inequality approximately holds; it always uses the lowest-weight edges that it can, but such edges do not in general connect the interior nodes of low-weight bounded-diameter trees. A new randomized greedy heuristic builds a bounded-diameter spanning tree from its center vertex or vertices. It chooses each next vertex at random but attaches the vertex with the lowest-weight eligible edge. This algorithm is faster than OTTC and yields substantially better solutions on Euclidean instances. An evolutionary algorithm encodes spanning trees as lists of their edges, augmented with their center vertices. It applies operators that maintain the diameter bound and always generate valid offspring trees. These operators are efficient, so the algorithm scales well to larger problem instances. On 25 Euclidean instances of up to 1000 vertices, the EA improved substantially on solutions found by the randomized greedy heuristic.
- A. Abdalla, N. Deo, and P. Gupta. Random-tree diameter and the diameter constrained MST. Congressus Numerantium, 144:161--182, 2000.]]Google Scholar
- K. Bala, K. Petropoulos, and T. E. Stern. Multicasting in a linear lightwave network. In IEEE INFOCOM'93, pages 1350--1358, 1993.]]Google ScholarCross Ref
- A. Bookstein and S. T. Klein. Compression of correlated bit-vectors. Information Systems, 16(4):110--118, 1996.]] Google ScholarDigital Library
- G. Chartrand and O. Oellermann. Applied and Algorithmic Graph Theory. McGraw-Hill, New York, 1993.]]Google Scholar
- G. Dahl. The 2-hop spanning tree problem. Technical Report 250, University of Oslo, 1997.]]Google Scholar
- N. Deo and A. Abdalla. Computing a diameter-constrained minimum spanning tree in parallel. In G. Bongiovanni, G. Gambosi, and R. Petreschi, editors, Algorithms and Complexity, number 1767 in LNCS, pages 17--31. Springer, Berlin, 2000.]] Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, 1979.]] Google ScholarDigital Library
- J. Gottlieb, B. A. Julstrom, F. Rothlauf, and G. R. Raidl. Prüfer numbers: A poor representation of spanning trees for evolutionary search. In L. Spector, E. Goodman, A. Wu, W. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon, and E. Burke, editors, Proceedings of the 2001 Genetic and Evolutionary Computation Conference, pages 343--350. Morgan Kaufmann, 2000.]]Google Scholar
- C. Jordan. Sur les assemblages des lignes. J. Reine Angew. Math., 70:185--190, 1869.]]Google ScholarCross Ref
- B. A. Julstrom. Encoding rectilinear Steiner trees as lists of edges. In G. Lamont, J. Carroll, H. Haddad, D. Morton, G. Papadopoulos, R. Sincovec, and A. Yfantis, editors, Proceedings of the 16th ACM Symposium on Applied Computing, pages 356--360. ACM Press, 2001.]] Google ScholarDigital Library
- G. Kortsarz and D. Peleg. Approximating shallow-light trees. In Proceedings of the 8th Symposium on Discrete Algorithms, pages 103--110, 1997.]] Google ScholarDigital Library
- G. Kortsarz and D. Peleg. Approximating the weight of shallow Steiner trees. Discrete Applied Mathematics, 93:265--285, 1999.]] Google ScholarDigital Library
- C. C. Palmer and A. Kershenbaum. Representing trees in genetic algorithms. In D. Schaffer, H.-P. Schwefel, and D. B. Fogel, editors, Proceedings of the First IEEE Conference on Evolutionary Computation, pages 379--384. IEEE Press, 1994.]]Google Scholar
- R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389--1401, 1957.]]Google ScholarCross Ref
- G. R. Raidl. An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem. In C. Fonseca, J.-H. Kim, and A. Smith, editors, Proceedings of the 2000 IEEE Congress on Evolutionary Computation, pages 104--111. IEEE Press, 2000.]]Google Scholar
- G. R. Raidl and B. A. Julstrom. Edge-sets: An effective evolutionary coding of spanning trees. IEEE Transactions on Evolutionary Computation. To appear.]]Google Scholar
- K. Raymond. A tree-based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, 7(1):61--77, 1989.]] Google ScholarDigital Library
- F. Rothlauf, D. Goldberg, and A. Heinzl. Network random keys - a tree network representation scheme for genetic and evolutionary algorithms. Evolutionary Computation, 10(1):75--97, 2002.]] Google ScholarDigital Library
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 for the bounded diameter minimum spanning tree problem
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 ...
Greedy heuristics and evolutionary algorithms for the bounded minimum-label spanning tree problem
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computationGiven an edge-labeled, connected, undirected graph G and a bound r>1, the bounded minimum-label spanning tree problem seeks a spanning tree on G whose edges carry the fewest possible labels and in which no label appears more than r times. Two greedy ...
Comments