english Steitz, Wolfgang; Rothlauf, Franz: New Insights into the OCST Problem: Integrating Node Degrees and their Location in the Graph, In: Guenther Raidl et al. (eds.): Proceedings of the Genetic and Evolutionary Computation Conference, Montreal, Canada, July 8-12, 2009. ACM Press, 2009


This paper considers the Euclidean variant of the optimal communciation spanning tree (OCST) problem. Researches have analyzed the structure of the problem and found that high quality solutions prefer edges of low cost. Further, edges pointing to the center of the network are more likely to be included in good solutions. We add to the literature and provide additional insights into the structure of the OCST problem. Therefore, we investigate properies of the whole tree, such as node degrees and the Wiener index. The results reveal that optimal solutions are structured in a star-like manner. There are few nodes with high node degrees, these nodes are located next to the graph's center. The majority of the nodes have very low node degrees. Especially, nodes with degree one are very common and located far away of the center. We exploit these insights to develop a construction heuristic, which builds spanning trees with similar properties. Experiments indicate a high solution quality for the OCST problem. In a next step, we seed the initial population of an evolutionary algorithm (EA) with solutions constructed with our method. An experimental study demonstrates the merits of using a biased initialization: the algorithm is faster, better compared to the same algorithm using random starting solutions.


optimal communications spanning tree problem, heuristics, evolutionary algorithm, construction heuristic


  author = \{Steitz, Wolfgang and Rothlauf, Franz},
  title = \{New Insights into the OCST Problem: Integrating Node Degrees and their Location in the Graph},
  year = \{2009},
  editor = \{Guenther Raidl et al.},
  booktitle = \{Proceedings of the Genetic and Evolutionary Computation Conference},
  publisher = \{ACM Press},
  url = \{},
  date = \{July 8-12, 2009},

BibTeX Download for BibTeX


EndNote Download for EndNote