Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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.
• 2: K. Bala, K. Petropoulos, and T. E. Stern. Multicasting in a linear lightwave network. In IEEE INFOCOM'93, pages 1350--1358, 1993.
• 3: A. Bookstein , S. T. Klein, Compression of correlated bit-vectors, Information Systems, v.16 n.4, p.387-400, 1991 [doi>10.1016/0306-4379(91)90030-D]
• 4: G. Chartrand and O. Oellermann. Applied and Algorithmic Graph Theory. McGraw-Hill, New York, 1993.
• 5: G. Dahl. The 2-hop spanning tree problem. Technical Report 250, University of Oslo, 1997.
• 6: Narsingh Deo , Ayman Abdalla, Computing a Diameter-Constrained Minimum Spanning Tree in Parallel, Proceedings of the 4th Italian Conference on Algorithms and Complexity, p.17-31, March 01, 2000
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 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.
• 9: C. Jordan. Sur les assemblages des lignes. J. Reine Angew. Math., 70:185--190, 1869.
• 10: Bryant A. Julstrom, Encoding rectilinear Steiner trees as lists of edges, Proceedings of the 2001 ACM symposium on Applied computing, p.356-360, March 2001, Las Vegas, Nevada, United States [doi>10.1145/372202.372365]
• 11: Guy Kortsarz , David Peleg, Approximating shallow-light trees, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.103-110, January 05-07, 1997, New Orleans, Louisiana, United States
• 12: Guy Kortsarz , David Peleg, Approximating the weight of shallow Steiner trees, Discrete Applied Mathematics, v.93 n.2-3, p.265-285, July 20, 1999 [doi>10.1016/S0166-218X(99)00111-0]
• 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.
• 14: R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389--1401, 1957.
• 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.
• 16: G. R. Raidl and B. A. Julstrom. Edge-sets: An effective evolutionary coding of spanning trees. IEEE Transactions on Evolutionary Computation. To appear.
• 17: Kerry Raymond, A tree-based algorithm for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.61-77, Feb. 1989 [doi>10.1145/58564.59295]
• 18: Franz Rothlauf , David E. Goldberg , Armin Heinzl, Network random keys: a tree representation scheme for genetic and evolutionary algorithms, Evolutionary Computation, v.10 n.1, p.75-97, Spring 2002 [doi>10.1162/106365602317301781]

INDEX TERMS

Keywords:
bounded-diameter spanning tree, edge-list encoding, greedy heuristics, local improvement, randomized heuristics