The multi-weighted Steiner tree problem

The authors formulate and investigate the Multi-Weighted Steiner Problem (MWS), a generalization of the Steiner problem in graphs, involving more than one weight function. As a special case, it contains the hierarchical network design problem. With the notion of ‘bottleneck length/distance’, a min-max measure, the authors analyze the interaction between differently weighted edges in a solution. Combining the results with known methods for the Steiner problem in graphs and the hierarchical network design problem, two heuristics for the MWS are developed, one based on weight modifications and the other on exchanging edges. Both are of time complexity O(kv²), with v the number of nodes and k the number of special nodes in the graph. The first is also suited for the directed MWS; the second is expected to perform better on the undirected version. Before actually solving the Steiner problem in graphs and the hierarchical network design problem, preprocessing techniques exploiting tests to reduce the problem graphs have proven to be valuable. The authors adapt three prominent tests for use in the MWS.