The multi-weighted Steiner tree problem (Q1179753)

A multi-weighted graph is a graph in which each edge \(e\) has 2 (\(k\), in general) weights, primary weight \(p(e)\) and secondary weight \(s(e)\) with \(p(e)\geq s(e)\). Let \(G=(V,E;p,s)\) be a multi-weighted graph, \(K\) be the special node set of \(V\), i.e. \(V\setminus K\) the non-special node set. The multi-weighted Steiner tree problem in this multi-weighted graph is the problem of finding a spanning tree \(T\) such that the sum of the primary weights of edges in \(T_ k\) and the secondary weights of edges in \(T\setminus T_ k\) is minimum, where \(T_ k\) is the subtree of \(T\) that covers the special node set \(K\). The multi-weighted Steiner tree problem is a generalization of the Steiner tree problem in graphs, and thus it is NP-hard. This paper develops two heuristic algorithms for the multi-weighted Steiner problem: one is based on weight modifications, the other on exchanging edges. Both of them are of time complexity \(O(| K| n^ 2)\), where \(n\) is the number of nodes in the graph.