The partial sum criterion for Steiner trees in graphs and shortest paths

The partial sum criterion for Steiner trees in graphs and shortest paths

0.00 Avg rating0 Votes
Article ID: iaor19991476
Country: Netherlands
Volume: 97
Issue: 1
Start Page Number: 172
End Page Number: 182
Publication Date: Feb 1997
Journal: European Journal of Operational Research
Authors: ,
Keywords: graphs
Abstract:

The partial sum criterion with parameter p adds up the p largest weights in the solution, giving the criterion value to be minimized. For p=1 the criterion is the bottleneck or minimax criterion. For the minimax Steiner tree problem in graphs we describe an O(|E|) algorithm with E being the set of edges in the problem graph. The algorithm unifies two existing algorithms, one of them solves the bottleneck shortest path problem and the other the bottleneck spanning tree problem. For the shortest path problem we consider the criterion for arbitrary values of p, defining it for solutions with less than p edges as the total sum. For an undirected graph with n nodes we present an O(n3) algorithm to determine, simultaneously, partial sum shortest paths between all pairs of nodes and for all values of the parameter p. For the 2-sum shortest path problem and one pair of nodes we give an O(|E|+n log n) algorithm. By exploiting this algorithm we obtain the same complexity for the 2-sum Steiner tree problem in graphs. Furthermore, we discuss the complexity of related problems and alternative partial sum criteria.

Reviews

Required fields are marked *. Your email address will not be published.