This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Rothlauf, F. Search for Related Content

On Optimal Solutions for the Optimal Communication Spanning Tree Problem

Department of Information Systems, University of Mainz, Mainz 55099, Germany
rothlauf{at}uni-mainz.de

This paper presents an experimental investigation into the properties of the optimal communication spanning tree (OCST) problem. The OCST problem seeks a spanning tree that connects all the nodes and satisfies their communication requirements at a minimum total cost. The paper compares the properties of random trees to the properties of the best solutions for the OCST problem that are found using an evolutionary algorithm. The results show, on average, that the optimal solution and the minimum spanning tree (MST) share a higher number of links than the optimal solution and a random tree. Furthermore, optimal solutions for OCST problems with randomly chosen distance weights share a higher number of links with an MST than OCST problems with Euclidean distance weights. This intuitive similarity between optimal solutions and MSTs suggests that some heuristic optimization methods for OCST problems might be improved by starting with an MST. Using an MST as a starting solution for a greedy search in the tested cases either improves median running time up to a factor of 10 while finding solutions of the same quality, or increases solution quality up to a factor of 100 while using the same number of search steps in comparison to starting the greedy search from a random tree. Starting a local search, a simulated annealing approach and a genetic algorithm from an MST increases solution quality up to a factor of three in comparison to starting from a random solution.

Subject classifications: networks/graphs; tree algorithms; communications; topological network design; simulation; statistical analysis.
History: Received March 2005; revision received August 2007; accepted December 2007.