Abstract
Reduction methods are a key ingredient of the most successful algorithms for the Steiner problem. Whereas classical reduction tests just considered single vertices or edges, recent and more sophisticated tests extend the scope of inspection to more general patterns. In this paper, we present such an extended reduction test, which generalizes different tests in the literature. We use the new approach of combining alternative-and bound-based methods, which substantially improves the impact of the tests. We also present several algorithmic contributions. The experimental results show a large improvement over previous methods using the idea of extension, leading to a drastic speed-up in the optimal solution process and the solution of several previously unsolved benchmark instances.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C.W. Duin. Steiner’s Problem in Graphs PhD thesis, Amsterdam University, 1993.
C.W. Duin. Preprocessing the Steiner problem in graphs. In D-Z. Du, J.M. Smith, and J.H. Rubinstein, editors, Advances in Steiner Trees, pages 173–233. Kluwer Academic Publishers, 2000
C.W. Duin and T. Volgenant. Reduction tests for the Steiner problem in graphs.Networks 19:549–567,1989.
F.K. Hwang, D.S. Richards, and P. Winter.The Steiner Tree Problem volume 53 of Annals of Discrete Mathematics North-Holland, Amsterdam,1992.
R.M. Karp. Reducibility among combinatorial problems.In R.E. Miller and J.W. Thatcher,editors,Complexity of Computer Computations pages 85–103.Plenum Press, New York,1972.
T. Koch and A. Martin. SteinLib.http://elib.zib.de/steinlib 1997.
T. Koch and A. Martin. Solving Steiner tree problems in graphs to optimality.Networks 32:207–232,1998.
K. Mehlhorn. A faster approximation algorithm for the Steiner problem in graphs.Information Processing Letters 27:125–128,1988.
T. Polzin and S. Vahdati Daneshmand. Extending reduction techniques for the Steiner tree problem:A combination of alternative-and bound-based approaches.Research Report MPI-I-2001-1-007, Max-Planck-Institut f ür Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany, 2001.
T. Polzin and S.Vahdat Daneshmand. Improved algorithms for the Steiner problem in networks.Discrete Applied Mathematics 112:263–300,2001.
T. Polzin and S.Vahdati Daneshmand.On Steiner trees and minimum spanning trees in hypergraphs.Research Report MPI-I-2001-1-005, Max-Planck-Institut f ür Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken,Germany, 2001.
T. Polzin and S.Vahdati Daneshmand. Partitioning techniques for the Steiner problem.Research Report MPI-I-2001-1-006,Max-Planck-Inst tut f ür Informatik, Stuhlsatzenhausweg 85,66123 Saarbrücken, Germany, 2001.
E. Uchoa. Algoritmos Para Problemas de Steiner com Aplicações em Projeto de Circuitos VLSI (in Portuguese). PhD thesis, Departamento De Informática, PUC-Rio,Rio de Janeiro, April 2001.
E. Uchoa, M. Poggi de Aragò, and C.C. Ribeiro.Preprocessing Steiner problems from VLSI layout,.Technical Report MCC.32/99, Departamento de Informática, PUC-Rio, Rio de Janeiro, Brasil,1999.
P. Winter.Reductions for the rectilinear Steiner tree problem.Networks 26:187–198,1995.
R.T. Wong.A dual ascent approach for Steiner tree problems on a directed graph.Mathematical Programming 28:271–287,1984.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Polzin, T., Daneshmand, S.V. (2002). Extending Reduction Techniques for the Steiner Tree Problem. In: Möhring, R., Raman, R. (eds) Algorithms — ESA 2002. ESA 2002. Lecture Notes in Computer Science, vol 2461. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45749-6_69
Download citation
DOI: https://doi.org/10.1007/3-540-45749-6_69
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44180-9
Online ISBN: 978-3-540-45749-7
eBook Packages: Springer Book Archive