research-article

Improved heuristics for the bounded-diameter minimum spanning tree problem

Authors:

Ashok K. GuptaAuthors Info & Claims

Soft Computing, Volume 11, Issue 10

Pages 911 - 921

https://doi.org/10.1007/s00500-006-0142-y

Published: 01 August 2007 Publication History

Abstract

Given an undirected, connected, weighted graph and a positive integer k, the bounded-diameter minimum spanning tree (BDMST) problem seeks a spanning tree of the graph with smallest weight, among all spanning trees of the graph, which contain no path with more than k edges. In general, this problem is NP-Hard for 4 ≤ k < n − 1, where n is the number of vertices in the graph. This work is an improvement over two existing greedy heuristics, called randomized greedy heuristic (RGH) and centre-based tree construction heuristic (CBTC), and a permutation-coded evolutionary algorithm for the BDMST problem. We have proposed two improvements in RGH/CBTC. The first improvement iteratively tries to modify the bounded-diameter spanning tree obtained by RGH/CBTC so as to reduce its cost, whereas the second improves the speed. We have modified the crossover and mutation operators and the decoder used in permutation-coded evolutionary algorithm so as to improve its performance. Computational results show the effectiveness of our approaches. Our approaches obtained better quality solutions in a much shorter time on all test problem instances considered.

References

[1]

Abdalla A, Deo N, and Gupta P Random-tree diameter and the diameter constrained MST Congr Numerantium 2000 144 161-182

[2]

Achuthan NR, Caccetta L, Cacetta P, Geelen JF (1992) Algorithms for the minimum weight spanning tree with bounded diameter problem. Optimization: techniques and applications, pp 297–304

[3]

Bala K, Petropoulos K, Stern TE (1993) Multicasting in a linear lightwave network. In: Proceedings of IEEE INFOCOM’93, pp 1350–1358

[4]

Bookstein A and Klein ST Compression of correlated bit- Inf Syst 1996 16 110-118

[5]

Davis L Handbook of genetic algorithms 1991 New York Van Nostrand Reinhold

[6]

Deo N, Abdalla A (2000) Computing a diameter-constrained minimum spanning tree in parallel. Lecture Notes in Computer Science, vol. Springer, Berlin Heidelberg New York, pp. 17–31

[7]

Garey MR and Johnson DS Computers and intractability: a guide to the theory of NP-completeness 1979 San Francisco W. H Freeman

[8]

Goldberg DE, Lingle JR (1985) Alleles, loci, and the travelling salesman problem. In: Proceedings of the First International Conference on Genetic Algorithms, pp 154–159

[9]

Julstrom BA, Raidl GR (2003) A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem. GECCO 2003 Workshops Proceedings, Workshop on Analysis and Design of Representations, pp 2–7

[10]

Julstrom BA (2004a) Encoding bounded-diameter spanning trees with permutations and with random keys. Lecture Notes in Computer Science, vol 3102. Springer, Berlin Heidelberg New York, pp 1272–1281

[11]

Julstrom BA (2004b) Greedy heuristics for the bounded-diameter minimum spanning tree problem. Communicated to ACM J Exp Algorithmics

[12]

Kortsarz G, Peleg D (1997) Approximating shallow-light trees. In: Proceedings of the 8th Symposium on Discrete Algorithms, pp 103–110

[13]

Kortsarz G and Peleg D Approximating the weight of shallow Steiner trees Discrete Appl Math 1999 93 265-285

[14]

Prim R Shortest connection networks and some generalizations Bell Syst Tech J 1957 36 1389-1401

[15]

Raidl GR and Julstrom BA Edge-sets: an effective evolutionary coding of spanning trees IEEE Trans Evol Comput 2003 7 225-239

[16]

Raidl GR, Julstrom BA (2003b) Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In: Proceedings of the 2003 ACM Symposium on Applied Computing, pp 747–752

[17]

Raymond K A tree-based algorithm for distributed mutual exclusion ACM Trans Comput Syst 1989 7 61-77

[18]

Reeves CR A genetic algorithm for flowshop sequencing Comput Oper Res 1995 22 5-13

[19]

Satyanarayanan R and Muthukrishnan DR A note on Raymond’s tree-based algorithm for distributed mutual exclusion Inf Process Letters 1992 43 249-255

[20]

Satyanarayanan R and Muthukrishnan DR A static tree-based algorithm for the distributed readers and writers problem Comput Sci Inform 1994 24 21-32

[21]

Wang S, Lang SD (1994) A tree-based distributed algorithm for the k-entry critical section problem. In: Proceedings of the 1994 International Conference on Parallel and Distributed Systems, pp 592–597

Cited By

Hong LZhong YLin JSilva SPaquete L(2023)Simulated Annealing Algorithm for the Bounded Diameter Minimum Spanning Tree ProblemProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3590575(215-218)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3590575
Lichen JCai LLi JLiu SPan PWang W(2023)Delay-constrained minimum shortest path trees and related problemsTheoretical Computer Science10.1016/j.tcs.2022.11.014941:C(191-201)Online publication date: 4-Jan-2023
https://dl.acm.org/doi/10.1016/j.tcs.2022.11.014
Singh KSundar S(2021)Artificial bee colony algorithm using permutation encoding for the bounded diameter minimum spanning tree problemSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-021-05913-z25:16(11289-11305)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00500-021-05913-z
Show More Cited By

Index Terms

Improved heuristics for the bounded-diameter minimum spanning tree problem

Index terms have been assigned to the content through auto-classification.

Recommendations

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 ...
An adaptive heuristic to the bounded-diameter minimum spanning tree problem

Given a graph G and a bound d 2, the bounded-diameter minimum spanning tree problem seeks a spanning tree on G of minimum weight subject to the constraint that its diameter does not exceed d . This problem is NP-hard; several heuristics have been ...
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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Soft Computing - A Fusion of Foundations, Methodologies and Applications

Soft Computing - A Fusion of Foundations, Methodologies and Applications Volume 11, Issue 10

Aug 2007

97 pages

ISSN:1432-7643

EISSN:1433-7479

Issue’s Table of Contents

© Springer-Verlag 2006.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 August 2007

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hong LZhong YLin JSilva SPaquete L(2023)Simulated Annealing Algorithm for the Bounded Diameter Minimum Spanning Tree ProblemProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3590575(215-218)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3590575
Lichen JCai LLi JLiu SPan PWang W(2023)Delay-constrained minimum shortest path trees and related problemsTheoretical Computer Science10.1016/j.tcs.2022.11.014941:C(191-201)Online publication date: 4-Jan-2023
https://dl.acm.org/doi/10.1016/j.tcs.2022.11.014
Singh KSundar S(2021)Artificial bee colony algorithm using permutation encoding for the bounded diameter minimum spanning tree problemSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-021-05913-z25:16(11289-11305)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00500-021-05913-z
Lichen JCai LLi JLiu SPan PWang W(2021)Delay-Constrained Minimum Shortest Path Trees and Related ProblemsCombinatorial Optimization and Applications10.1007/978-3-030-92681-6_53(676-686)Online publication date: 17-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-92681-6_53
Singh KSundar S(2018)A Heuristic for the Bounded Diameter Minimum Spanning Tree ProblemProceedings of the 2nd International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence10.1145/3206185.3206202(84-88)Online publication date: 24-Mar-2018
https://dl.acm.org/doi/10.1145/3206185.3206202
(2015)New Heuristic Approaches for the Bounded-Diameter Minimum Spanning Tree ProblemINFORMS Journal on Computing10.5555/2736026.273602727:1(151-163)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.5555/2736026.2736027
(2015)New Heuristic Approaches for the Bounded-Diameter Minimum Spanning Tree ProblemINFORMS Journal on Computing10.5555/2736024.273602527:1(151-163)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.5555/2736024.2736025
(2015)New Heuristic Approaches for the Bounded-Diameter Minimum Spanning Tree ProblemINFORMS Journal on Computing10.5555/2725954.272596527:1(151-163)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.5555/2725954.2725965
Anderson RStenger BCipolla R(2014)Using Bounded Diameter Minimum Spanning Trees to Build Dense Active Appearance ModelsInternational Journal of Computer Vision10.1007/s11263-013-0661-9110:1(48-57)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1007/s11263-013-0661-9
Akbari Torkestani J(2014)A stable virtual backbone for wireless MANETSTelecommunications Systems10.1007/s11235-013-9760-855:1(137-148)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1007/s11235-013-9760-8
Show More Cited By

View Options

View options

Get Access

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents