Paper Info
Title
Improved heuristics for the bounded-diameter minimum spanning tree problem
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.
Year
DOI
Venue
2007
10.1007/s00500-006-0142-y
Soft Comput.
Keywords
Field
DocType
Bounded-diameter minimum spanning tree problem,Constrained optimization,Greedy heuristic,Steady-state genetic algorithm,Uniform order-based crossover
Discrete mathematics,Combinatorics,Mathematical optimization,k-minimum spanning tree,Euclidean minimum spanning tree,Spanning tree,Connected dominating set,Shortest-path tree,Reverse-delete algorithm,Kruskal's algorithm,Mathematics,Minimum spanning tree
Journal
Volume
Issue
ISSN
11
10
1432-7643
Citations 
PageRank 
References 
19
0.95
11
Authors
2
Name
Order
Citations
PageRank
Alok Singh120117.15
Ashok K. Gupta2607.32