Orientation matters: How to efficiently solve OCSTproblems with problem-specific EAs

The optimal communication spanning tree (OCST) problemis a well known NP-hard combinatorial optimizationproblem which seeks a spanning tree that satisfies all givencommunication requirements for minimal total costs. Ithas been shown that optimal solutions of OCST problemsare biased towards the much simpler minimum spanningtree (MST) problem. Therefore, problem-specific representationsfor EAs like heuristic variants of edge-sets that arebiased towards MSTs show high performance.In this paper, additional properties of optimal solutionsfor Euclidean variants of OCST problems are studied. Experimentalresults show that not only edges in optimal treesare biased towards low-distance weights but also edges whichare directed towards the graph’s center are overrepresentedin optimal solutions.[...]