Given a set
S of starting vertices and a set
T of terminating vertices in a graph
G = (
V,
E) with non-negative weights on edges, the
minimum Steiner network problem is to find a subgraph of
G with the minimum total edge weight. In such a subgraph, we require that for each vertex
s
S and
t
T, there is a path from
s to a terminating vertex as well as a path from a starting vertex to
t. This problem can easily be proven NP-hard. For solving the minimum Steiner network problem, we first present an algorithm that runs in time and space that both are polynomial in
n with constant degrees, but exponential in |
S|+|
T|, where
n is the number of vertices in
G. Then we present an algorithm that uses space that is quadratic in
n and runs in time that is polynomial in
n with a degree O(max {max {|
S|,|
T|}–2,min {|
S|,|
T|}–1}). In spite of this degree, we prove that the number of Steiner vertices in our solution can be as large as |
S|+|
T|–2. Our algorithm can enumerate all possible optimal solutions. The input graph
G can either be undirected or directed acyclic. We also give a linear time algorithm for the special case when min {|
S|,|
T|} = 1 and max {|
S|,|
T|} = 2.The
minimum union paths problem is similar to the minimum Steiner network problem except that we are given a set
H of hitting vertices in
G in addition to the sets of starting and terminating vertices. We want to find a subgraph of
G with the minimum total edge weight such that the conditions required by the minimum Steiner network problem are satisfied as well as the condition that every hitting vertex is on a path from a starting vertex to a terminating vertex. Furthermore,
G must be directed acyclic. For solving the minimum union paths problem, we also present algorithms that have a time and space tradeoff similar to algorithms for the minimum Steiner network problem. We also give a linear time algorithm for the special case when |
S| = 1, |
T| = 1 and |
H| = 2.An extended abstract of part of this paper appears in Hsu et al. (1996).Supported in part by the National Science Foundation under Grants CCR-9309743 and INT-9207212, and by the Office of Naval Research under Grant No. N00014-93-1-0272.Supported in part by the National Science Council, Taiwan, ROC, under Grant No. NSC-83-0408-E-001-021.
相似文献