×

Two variations of the minimum Steiner problem. (English) Zbl 1066.90105

Summary: 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 \in S\) and \(t {\in} 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\).

MSC:

90C27 Combinatorial optimization
90B10 Deterministic network models in operations research
05C35 Extremal problems in graph theory
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Y.P. Aneja ?An integer linear programming approachto the Steiner problem in graphs,?Networks, vol. 10, pp. 167-178, 1980. · Zbl 0445.90087 · doi:10.1002/net.3230100207
[2] G. Dahl ?Directed Steiner problems with connectivity constraints,?Discrete Applied Math., vol. 47, pp. 109-128, 1993. · Zbl 0789.68106 · doi:10.1016/0166-218X(93)90086-4
[3] S.E. Dreyfus and R.A. Wagner ?The Steiner problem in graphs,?Networks, vol. 1, pp. 195-207, 1972. · Zbl 0229.05125 · doi:10.1002/net.3230010302
[4] M.L. Fredman and R.E. Tarjan ?Fibonacci heaps and their uses in improved network optimization algorithms,?Journal of ACM, vol. 34, no. 3, pp. 596-615, 1987. · doi:10.1145/28869.28874
[5] H.N. Gabow, Z. Galil, T. Spencer, and R.E. Tarjan ?Efficient algorithms for finding minimum spanning trees in undirected and directed graphs,?Combinatorica, vol. 6, no. 2, pp. 109-122, 1986. · Zbl 0608.05027 · doi:10.1007/BF02579168
[6] S.L. Hakimi ?Steiner?s problem in graphs and its applications,?Networks, vol. 1, pp. 113-133, 1971. · Zbl 0229.05124 · doi:10.1002/net.3230010203
[7] T.-S. Hsu, K.-H. Tsai, D.-W. Wang, and D.T. Lee ?Steiner problems on directed acyclic graphs,?in Lecture Notes in Computer Science 1090: Proceedings of the 2nd International Symposium on Computing and Combinatorics, J.Y. Cai and C.K. Wong (Ed.), Springer-Verlag: New York, NY, 1996, pp. 21-30.
[8] F.K. Hwang and D.S. Richards ?Steiner tree problems,?Networks, vol. 22, pp. 55-89, 1992. · Zbl 0749.90082 · doi:10.1002/net.3230220105
[9] F.K. Hwang, D.S. Richards, and P. Winter The Steiner Tree Problem, Annals of Discrete Mathematics, vol. 53, North-Holland, 1992. · Zbl 0774.05001
[10] E.L. Lawler Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston: New York, 1976.
[11] S. Martello and P. Toth ?Finding a minimum equivalent graph of a digraph,?Networks, vol.12, pp. 89-100, 1982. · Zbl 0484.68049 · doi:10.1002/net.3230120202
[12] L. Nastansky, S.M. Selkow, and N.F. Stewart ?Cost-minimal trees in directed acyclic graphs,? Zeitschrift für Operations Research, 1974, pp. 59-67. · Zbl 0273.90059
[13] S.K. Rao, P. Sadayappan, F.K. Hwang, and P.W. Shor ?The rectilinear Steiner arborescence problem,?Algorithmica, 1992, pp. 277-288. · Zbl 0773.05041
[14] R.E. Tarjan Data Structures and Network Algorithms, SIAM Press, Philadelphia, PA, 1983.
[15] S. Voss ?Worst-case performance of some heuristics for Steiner?s problem in directed graphs,? Information Processing Letters, vol. 48, pp. 99-105, 1993. · Zbl 0788.68111 · doi:10.1016/0020-0190(93)90185-C
[16] P. Winter ?Steiner problem in networks: A survey,?Networks, vol. 17, pp. 129-167, 1987. · Zbl 0646.90028 · doi:10.1002/net.3230170203
[17] R.T. Wong ?A dual ascent approach for Steiner tree problems on a directed graphs,?Mathematical Programming, vol. 28, pp. 271-287, 1984. · Zbl 0532.90092 · doi:10.1007/BF02612335
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.