skip to main content
10.1145/952532.952678acmconferencesArticle/Chapter ViewAbstractPublication PagessacConference Proceedingsconference-collections
Article

Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem

Published:09 March 2003Publication History

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.

References

  1. A. Abdalla, N. Deo, and P. Gupta. Random-tree diameter and the diameter constrained MST. Congressus Numerantium, 144:161--182, 2000.]]Google ScholarGoogle Scholar
  2. K. Bala, K. Petropoulos, and T. E. Stern. Multicasting in a linear lightwave network. In IEEE INFOCOM'93, pages 1350--1358, 1993.]]Google ScholarGoogle ScholarCross RefCross Ref
  3. A. Bookstein and S. T. Klein. Compression of correlated bit-vectors. Information Systems, 16(4):110--118, 1996.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. G. Chartrand and O. Oellermann. Applied and Algorithmic Graph Theory. McGraw-Hill, New York, 1993.]]Google ScholarGoogle Scholar
  5. G. Dahl. The 2-hop spanning tree problem. Technical Report 250, University of Oslo, 1997.]]Google ScholarGoogle Scholar
  6. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  7. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  8. 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 ScholarGoogle Scholar
  9. C. Jordan. Sur les assemblages des lignes. J. Reine Angew. Math., 70:185--190, 1869.]]Google ScholarGoogle ScholarCross RefCross Ref
  10. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  11. G. Kortsarz and D. Peleg. Approximating shallow-light trees. In Proceedings of the 8th Symposium on Discrete Algorithms, pages 103--110, 1997.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. G. Kortsarz and D. Peleg. Approximating the weight of shallow Steiner trees. Discrete Applied Mathematics, 93:265--285, 1999.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. 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 ScholarGoogle Scholar
  14. R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389--1401, 1957.]]Google ScholarGoogle ScholarCross RefCross Ref
  15. 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 ScholarGoogle Scholar
  16. G. R. Raidl and B. A. Julstrom. Edge-sets: An effective evolutionary coding of spanning trees. IEEE Transactions on Evolutionary Computation. To appear.]]Google ScholarGoogle Scholar
  17. K. Raymond. A tree-based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, 7(1):61--77, 1989.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. 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 ScholarGoogle ScholarDigital LibraryDigital Library

Recommendations

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Sign in
  • Published in

    cover image ACM Conferences
    SAC '03: Proceedings of the 2003 ACM symposium on Applied computing
    March 2003
    1268 pages
    ISBN:1581136242
    DOI:10.1145/952532

    Copyright © 2003 ACM

    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    • Published: 9 March 2003

    Permissions

    Request permissions about this article.

    Request Permissions

    Check for updates

    Qualifiers

    • Article

    Acceptance Rates

    Overall Acceptance Rate1,650of6,669submissions,25%

    Upcoming Conference

    SAC '24

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader