6533b874fe1ef96bd12d6002

RESEARCH PRODUCT

New insights into the OCST problem

subject

description

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.