Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Euclidean and Minkowski Steiner Trees Read chapter Read first chapter

2015 | OriginalPaper | Chapter

5. Steiner Trees in Graphs and Hypergraphs

Authors : Marcus Brazil, Martin Zachariasen

Published in: Optimal Interconnection Trees in the Plane

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this chapter we consider two combinatorial versions of the Steiner tree problem: the Steiner tree problem in graphs and the Steiner tree problem in hypergraphs. Also, we consider the minimum spanning tree problem in hypergraphs. Although this book focuses on geometric interconnection problems in the plane, these combinatorial problems are included for several reasons. Firstly, the Steiner tree problem in graphs is probably the best studied of all the many variants of the Steiner tree problem. Secondly, the fixed orientation Steiner tree problem in the plane (and specifically the rectilinear Steiner tree problem in the plane) can be reduced to the Steiner tree problem in graphs. Thirdly, the full Steiner tree concatenation phase of GeoSteiner, the most efficient exact algorithm for computing minimum Steiner trees in the plane, can be reduced to either the Steiner tree problem in graphs or the minimum spanning tree problem in hypergraphs.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Steiner Trees with Other Cost Functions and Constraints
Footnotes
1
The Steiner tree problem in graphs was originally formulated by Hakimi [185] (and independently by Levin [251]) in 1971. In the literature the problem is sometimes called the Steiner problem in networks (and the graph version is reserved for the unweighted case). Exact algorithms based on enumeration and dynamic programming were first proposed by Hakimi [185], Levin [251] and Dreyfus and Wagner [131].
 
2
For hypergraphs with edges of size 3, there exists a polynomial-time algorithm for the unweighted case [268, 315]. Note that for a different definition of the minimum spanning tree problem in a hypergraph, Tomescu and Zimand [369] have shown that the problem is NP-hard for hypergraphs with edges of size 3.
 
Literature
15.
31.
98.
Chopra, S., Gorres, E., Rao, M.R.: Solving the Steiner tree problem on a graph using branch and cut. ORSA J. Comput. 4, 320–335 (1992)CrossRefMATH
99.
Chopra, S., Rao, M.R.: The Steiner tree problem I: formulations, compositions and extension of facets. Math. Program. 64, 209–229 (1994)CrossRefMATHMathSciNet
100.
112.
113.
131.
134.
Du, D.-Z., Hu, X.-D.: Steiner Tree Problems in Computer Communication Networks. World Scientific, Singapore (2008)CrossRefMATH
140.
Duin, C.W.: Steiner’s problem in graphs – approximation, reduction, variation. PhD thesis, University of Amsterdam (1993)
141.
Duin, C.W.: Preprocessing the Steiner problem in graphs. In: Du, D.-Z., Smith, J.M., Rubinstein, J.H. (eds.) Advances in Steiner Trees, pp. 173–233. Kluwer Academic, Boston (2000)
142.
143.
147.
Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Guy, R.K. (ed.) Combinatorial Structures and Their Applications, pp. 69–87. Gordon and Breach, New York (1970)
153.
Fößmeier, U., Kaufmann, M.: On exact solutions for the rectilinear Steiner tree problem. Technical report WSI-96-09, Universität Tübingen (1996)
154.
Fößmeier, U., Kaufmann, M.: Solving rectilinear Steiner tree problems exactly in theory and practice. In: Burkard, R., Woeginger, G. (eds.) Algorithms – ESA’97, Graz. Lecture Notes in Computer Science, vol. 1284, pp. 171–185. Springer, Berlin/Heidelberg (1997)
158.
Fuchs, B., Kern, W., Molle, D., Richter, S., Rossmanith, P., Wang, X.: Dynamic programming for minimum Steiner trees. Theory Comput. Syst. 41(3), 493–500 (2007)CrossRefMATHMathSciNet
159.
Fuchs, B., Kern, W., Wang, X.: The number of tree stars is O ∗(1. 357 k ). Electron. Notes Discret. Math. 25, 183–185 (2006)
161.
Ganley, J.L., Cohoon, J.P.: A faster dynamic programming algorithm for exact rectilinear Steiner minimal trees. In: Proceedings of the Fourth Great Lakes Symposium on VLSI, South Bend, pp. 238–241 (1994)
162.
Ganley, J.L., Cohoon, J.P.: Optimal rectilinear Steiner minimal trees in o(n 22. 62 n ) time. In: Proceedings of the Sixth Canadian Conference on Computational Geometry, Saskatoon, pp. 308–313 (1994)
164.
Ganley, J.L., Cohoon, J.P.: Improved computation of optimal rectilinear Steiner minimal trees. Int. J. Comput. Geom. Appl. 7(5), 457–472 (1997)CrossRefMATHMathSciNet
169.
180.
181.
Goemans, M.X., Bertsimas, D.J.: Survivable networks, linear programming relaxations and the parsimonious property. Math. Program. 60, 145–166 (1993)CrossRefMATHMathSciNet
182.
185.
203.
Hougardy, S., Silvanus, J., Vygen, J.: Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm. Technical report, Research Institute for Discrete Mathematics, University of Bonn (2014)
204.
Huang, T., Li, L., Young, E.F.Y.: On the construction of optimal obstacle-avoiding rectilinear Steiner minimum trees. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 30(5), 718–731 (2011)CrossRef
211.
Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem. Annals of Discrete Mathematics, vol. 53. Elsevier, Amsterdam (1992)
231.
Karp, R.M.: Reducibility among combinatorial problems. In: Thatcher, J.W. (ed.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)CrossRef
234.
237.
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Algorithms and Combinatorics, 4th edn. Springer, Berlin (2008)
251.
Levin, A.Y.: Algorithm for the shortest connection of a group of graph vertices. Sov. Math. Dokl. 12, 1477–1481 (1971)MATH
268.
Lovász, L.: The matroid matching problem. Algebraic methods in graph theory. Colloquia Mathematica Societatis János Bolyai, Szeged (1978)
270.
Magnanti, T.L., Wolsey, L.A.: Optimal trees. In: Monma, C.L., Ball, M.O., Magnanti, T.L., Nemhauser, G.L. (eds.) Network Models. Handbooks in Operations Research and Management Science, vol. 7, pp. 503–615. Elsevier, Amsterdam (1995)
306.
Polzin, T.: Algorithms for the Steiner problem in networks. PhD thesis, Universität des Saarlandes (2003)
307.
Polzin, T., Vahdati Daneshmand, S.: A comparison of Steiner tree relaxations. Discret. Appl. Math. 112, 241–261 (2001)CrossRefMATH
308.
Polzin, T., Vahdati Daneshmand, S.: Improved algorithms for the Steiner problem in networks. Discret. Appl. Math. 112, 263–300 (2001)CrossRefMATH
309.
Polzin, T., Vahdati Daneshmand, S.: Extending reduction techniques for the Steiner tree problem. In: Möhring, R., Raman, R. (eds.) Algorithms – ESA 2002, Rome. Lecture Notes in Computer Science, vol. 2461, pp. 795–807. Springer, Berlin/Heidelberg (2002)CrossRef
310.
Polzin, T., Vahdati Daneshmand, S.: On Steiner trees and minimum spanning trees in hypergraphs. Oper. Res. Lett. 31, 12–20 (2003)CrossRefMATHMathSciNet
311.
Polzin, T., Vahdati Daneshmand, S.: Approaches to the Steiner problem in networks. Lect. Notes Comput. Sci. 5515, 81–103 (2009)CrossRef
315.
Prömel, H.J., Steger, A.: RNC-approximation algorithms for the Steiner problem. In: Proceedings of the STACS’97, Lübeck. Lecture Notes in Computer Science, vol. 1200, pp. 559–570. Springer, Berlin/Heidelberg (1997)
316.
Prömel, H.J., Steger, A.: The Steiner Tree Problem: A Tour Through Graphs, Algorithms, and Complexity. Advanced Lectures in Mathematics. Friedrick Vieweg and Son, Berlin (2002)CrossRef
332.
369.
373.
375.
Vahdati Daneshmand, S.: Algorithmic approaches to the Steiner problem in networks. PhD thesis, Universität Mannheim (2004)
379.
386.
Warme, D.M.: Spanning trees in hypergraphs with applications to Steiner trees. PhD thesis, University of Virginia (1998)
402.
404.
407.
409.
Wong, R.: A dual ascent approach for Steiner tree problems on a directed graph. Math. Program. 28, 271–287 (1984)CrossRefMATH
423.
433.
Zachariasen, M., Winter, P.: Obstacle-avoiding Euclidean Steiner trees in the plane: an exact algorithm. In: Workshop on Algorithm Engineering and Experimentation (ALENEX), Baltimore. Lecture Notes in Computer Science 1619, pp. 282–295. Springer, Berlin/Heidelberg (1999)
Metadata
Title
Steiner Trees in Graphs and Hypergraphs
Authors
Marcus Brazil
Martin Zachariasen
Copyright Year
2015
Book
Optimal Interconnection Trees in the Plane

Print ISBN: 978-3-319-13914-2

Electronic ISBN: 978-3-319-13915-9

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-13915-9_5

Premium Partner

    Image Credits