Faster Algorithms for Steiner Tree and Related Problems: From Theory to Practice | SpringerLink
Skip to main content
Springer Nature Link
Log in

Faster Algorithms for Steiner Tree and Related Problems: From Theory to Practice

  • Conference paper
  • First Online:
Operations Research Proceedings 2022 (OR 2022)

Part of the book series: Lecture Notes in Operations Research ((LNOR))

Included in the following conference series:

  • 838 Accesses

Abstract

The Steiner tree problem in graphs (SPG) is a classic \(\mathcal{N}\mathcal{P}\)-hard problem. Many applications can be modeled as SPG or closely related problems. This article describes a state-of-the-art solver for finding optimal solutions to classic Steiner tree and 14 related problem classes. It was developed as part of the author’s doctoral dissertation.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    https://scipjack.zib.de/.

  2. 2.

    https://pacechallenge.org/2018/.

References

  1. Byrka, J., Grandoni, F., Rothvoss, T., & Sanità, L. (2013). Steiner tree approximation via iterative randomized rounding. The Journal of the ACM, 60(1), 6.

    Google Scholar 

  2. Daneshmand, S. V. (2004). Algorithmic approaches to the Steiner problem in networks. PhD thesis, Universität Mannheim.

    Google Scholar 

  3. Dimacs challenge 2014. https://dimacs11.zib.de/. Accessed October 18, 2022.

  4. Dreyfus, S. E., & Wagner, R. A. (1971). The Steiner problem in graphs. Networks, 1(3), 195–207.

    Article  Google Scholar 

  5. Erickson, Ranel E., Monma, Clyde L., & Veinott, Arthur F. (1987). Send-and-split method for minimum-concave-cost network flows. Mathematics of Operations Research, 12(4), 634–664.

    Article  Google Scholar 

  6. Goemans, M. X., Olver, N., Rothvoß, T., & Zenklusen, R. (2012). Matroids and integrality gaps for hypergraphic steiner tree relaxations. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, pp. 1161-1176, New York, NY, USA, 2012. Association for Computing Machinery.

    Google Scholar 

  7. Hougardy, Stefan, Silvanus, Jannik, & Vygen, Jens. (2017). Dijkstra meets Steiner: A fast exact goal-oriented Steiner tree algorithm. Mathematical Programming Computation, 9(2), 135–202.

    Article  Google Scholar 

  8. Hwang, F. K., Richards, D. S., & Winter, P. (1992). The Steiner Tree Problem. Annals of Discrete Mathematics: Elsevier Science.

    Google Scholar 

  9. Iwata, Yoichi, & Shigemura, Takuto. (2019). Separator-based pruned dynamic programming for Steiner tree. In Proceedings of the AAAI Conference on Artificial Intelligence, 33, 1520–1527.

    Article  Google Scholar 

  10. Juhl, D., Warme, D. M., Winter, P., & Zachariasen, M. (2018). The GeoSteiner software package for computing Steiner trees in the plane: An updated computational study. Mathematical Programming Computation, 10(4):487–532.

    Google Scholar 

  11. Kisfaludi-Bak, S., Nederlof, J., & van Leeuwen, E. J. (2020). Nearly ETH-tight algorithms for planar Steiner tree with terminals on few faces. ACM Transactions on Algorithms (TALG), 16(3), 1–30.

    Google Scholar 

  12. Koch, Thorsten, & Martin, Alexander. (1998). Solving Steiner tree problems in graphs to optimality. Networks, 32, 207–232.

    Article  Google Scholar 

  13. Ljubić, Ivana. (2021). Solving steiner trees: Recent advances, challenges, and perspectives. Networks, 77(2), 177–204.

    Article  Google Scholar 

  14. Nederlof, J. (2009). Fast polynomial-space algorithms using Möbius inversion: Improving on Steiner tree and related problems. In International Colloquium on Automata, Languages, and Programming, pp. 713–725. Springer.

    Google Scholar 

  15. Pace challenge 2018. https://pacechallenge.org/2018/. Accessed October 18, 2022.

  16. Polzin, T. (2003). Algorithms for the Steiner problem in networks. PhD thesis, Saarland University.

    Google Scholar 

  17. Rehfeldt, D. (2021). Faster algorithms for Steiner tree and related problems: From theory to practice. PhD thesis, Technische Universität Berlin.

    Google Scholar 

  18. Rehfeldt, D., & Koch, T. (2019). Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem. SIAM Journal on Optimization, 29(1), 369–398.

    Article  Google Scholar 

  19. Rehfeldt, D., & Koch, T. (2021). Implications, conflicts, and reductions for steiner trees. Mathematical Programming, pp. 1–64.

    Google Scholar 

  20. Rehfeldt, D., & Koch, T. (2022). On the exact solution of prize-collecting steiner tree problems. INFORMS Journal on Computing, 34(2), 872–889.

    Google Scholar 

  21. Rehfeldt, D., Franz, H., & Koch, T. (2022). Optimal connected subgraphs: Integer programming formulations and polyhedra. Networks, 80(3), 314–332.

    Google Scholar 

  22. Shinano, Y., Rehfeldt, D., & Koch, T. (2019). Building optimal steiner trees on supercomputers by using up to 43,000 cores. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019, 11494, pp. 529 – 539.

    Google Scholar 

  23. Takahashi, H., & Matsuyama, A. (1980). An approximate solution for the Steiner problem in graphs. Mathematica Japonicae, 24, 573–577.

    Google Scholar 

  24. Uchoa, E., & Werneck, R. F. F. (2010). Fast Local Search for Steiner Trees in Graphs. In G. E. Blelloch & D. Halperin (Eds). editors, ALENEX, pp. 1–10. SIAM Journal of Applied Mathematics.

    Google Scholar 

  25. Vygen, Jens. (2011). Faster algorithm for optimum Steiner trees. Information Processing Letters, 111(21), 1075–1079.

    Article  Google Scholar 

  26. Wong, R. T. (1984). A dual ascent approach for Steiner tree problems on a directed graph. Mathematical Programming, 28, 271–287.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Zuse Institute Berlin, Takustr. 7, 14195, Berlin, Germany

    Daniel Rehfeldt

Authors
  1. Daniel Rehfeldt
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniel Rehfeldt .

Editor information

Editors and Affiliations

  1. Institute for Operations Research, Karlsruhe Institute of Technology, Karlsruhe, Germany

    Oliver Grothe

  2. Institute for Operations Research, Karlsruhe Institute of Technology, Karlsruhe, Germany

    Stefan Nickel

  3. Institute for Operations Research, Karlsruhe Institute of Technology, Karlsruhe, Germany

    Steffen Rebennack

  4. Institute for Operations Research, Karlsruhe Institute of Technology, Karlsruhe, Germany

    Oliver Stein

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Rehfeldt, D. (2023). Faster Algorithms for Steiner Tree and Related Problems: From Theory to Practice. In: Grothe, O., Nickel, S., Rebennack, S., Stein, O. (eds) Operations Research Proceedings 2022. OR 2022. Lecture Notes in Operations Research. Springer, Cham. https://doi.org/10.1007/978-3-031-24907-5_3

Download citation

Publish with us

Policies and ethics

Search

Navigation