### Greedy heuristics for the bounded diameter minimum spanning tree problemGreedy heuristics for the bounded diameter minimum spanning tree problem

Access Restriction
Subscribed

 Author Julstrom, Bryant A. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Bounded-diameter minimum spanning tree problem ♦ Diameter ♦ Greedy heuristics ♦ Spanning trees Abstract Given a connected, weighted, undirected graph $\textit{G}$ and a bound $\textit{D},$ the bounded diameter minimum spanning tree problem seeks a spanning tree on $\textit{G}$ of minimum weight among the trees in which no path between two vertices contains more than $\textit{D}$ edges. In Prim's algorithm, the diameter of the growing spanning tree can always be known, so it is a good starting point from which to develop greedy heuristics for the bounded diameter problem. Abdalla, Deo, and Gupta described such an algorithm. It imitates Prim's algorithm but avoids edges whose inclusion in the spanning tree would violate the diameter bound. Running the algorithm from one start vertex requires time that is $O(n^{3}).$ A modification of this approach uses the start vertex as the center of the spanning tree (if $\textit{D}$ is even) or as one of the two center vertices (if $\textit{D}$ is odd). This yields a simpler algorithm whose time is $O(n^{2}).$ A further modification chooses each next vertex at random rather than greedily, though it still connects each vertex to the growing tree with the lowest-weight feasible edge. On Euclidean problem instances with small diameter bounds, the randomized heuristic is superior to the two fully greedy algorithms, though its advantage fades as the diameter bound grows. On instances whose edge weights have been chosen at random, the fully greedy algorithms outperform the randomized heuristic. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2010-01-05 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 14 Page Count 14 Starting Page 1.1 Ending Page 1.14

#### Open content in new tab

Source: ACM Digital Library