Variations of the prize-collecting Steiner tree problem

Variations of the prize-collecting Steiner tree problem

0.00 Avg rating0 Votes
Article ID: iaor2007922
Country: United States
Volume: 47
Issue: 4
Start Page Number: 199
End Page Number: 205
Publication Date: Jul 2006
Journal: Networks
Authors: ,
Keywords: Steiner problem
Abstract:

The prize-collecting Steiner tree problem is well known to be NP-hard. We consider seven variations of this problem generalizing several well-studied bottleneck and minsum problems with feasible solutions as trees of a graph. Four of these problems are shown to be solvable in O(m+n log n) time and the remaining are shown to be NP-hard where n is the number of nodes and m is the number of edges in the underlying graph. For one of these polynomially solvable cases, we also provide an O(m) algorithm generalizing and unifying known linear time algorithms for the bottleneck spanning tree problem, bottleneck s-t path problem, and bottleneck Steiner tree problem.

Reviews

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