nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

6. Spanning Trees and Arborescences

verfasst von : Bernhard Korte, Jens Vygen

Erschienen in: Combinatorial Optimization

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Consider a telephone company that wants to rent a subset from an existing set of cables, each of which connects two cities. The rented cables should suffice to connect all cities and they should be as cheap as possible. It is natural to model the network by a graph: the vertices are the cities and the edges correspond to the cables. By Theorem 2.4 the minimal connected spanning subgraphs of a given graph are its spanning trees. So we look for a spanning tree of minimum weight, where we say that a subgraph T of a graph G with weights \(c: E(G) \rightarrow \mathbb{R}\) has weight c(E(T)) = ∑ _{e ∈ E(T)} c(e). We shall refer to c(e) also as the cost of e.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Integer Programming

Nächstes Kapitel Shortest Paths

Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. [1993]: Network Flows. Prentice-Hall, Englewood Cliffs 1993, Chapter 13

Balakrishnan, V.K. [1995]: Network Optimization. Chapman and Hall, London 1995, Chapter 1

Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. [2009]: Introduction to Algorithms. Third Edition. MIT Press, Cambridge 2009, Chapter 23

Gondran, M., and Minoux, M. [1984]: Graphs and Algorithms. Wiley, Chichester 1984, Chapter 4

Magnanti, T.L., and Wolsey, L.A. [1995]: Optimal trees. In: Handbooks in Operations Research and Management Science; Volume 7: Network Models (M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser, eds.), Elsevier, Amsterdam 1995, pp. 503–616

Schrijver, A. [2003]: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin 2003, Chapters 50–53

Tarjan, R.E. [1983]: Data Structures and Network Algorithms. SIAM, Philadelphia 1983, Chapter 6

Wu, B.Y., and Chao, K.-M. [2004]: Spanning Trees and Optimization Problems. Chapman & Hall/CRC, Boca Raton 2004

Bock, F.C. [1971]: An algorithm to construct a minimum directed spanning tree in a directed network. In: Avi-Itzhak, B. (Ed.): Developments in Operations Research, Volume I. Gordon and Breach, New York 1971, pp. 29–44

Borůvka, O. [1926a]: O jistém problému minimálním. Práca Moravské Pr̆írodovĕdecké Spolnec̆nosti 3 (1926), 37–58 [in Czech]

Borůvka, O. [1926b]: Pr̆íspevĕk k r̆es̆ení otázky ekonomické stavby. Elektrovodních sítí. Elektrotechnicky Obzor 15 (1926), 153–154 [in Czech]

Cayley, A. [1889]: A theorem on trees. Quarterly Journal on Mathematics 23 (1889), 376–378

Chazelle, B. [2000]: A minimum spanning tree algorithm with inverse-Ackermann type complexity. Journal of the ACM 47 (2000), 1028–1047

Cheriton, D., and Tarjan, R.E. [1976]: Finding minimum spanning trees. SIAM Journal on Computing 5 (1976), 724–742

Chu, Y., and Liu, T. [1965]: On the shortest arborescence of a directed graph. Scientia Sinica 4 (1965), 1396–1400; Mathematical Review 33, # 1245

Conforti, M., Cornuéjols, G., and Zambelli, G. [2010]: Extended formulations in combinatorial optimization. 4OR 8 (2010), 1–48

Diestel, R. [1997]: Graph Theory. Springer, New York 1997

Dijkstra, E.W. [1959]: A note on two problems in connexion with graphs. Numerische Mathematik 1 (1959), 269–271

Dixon, B., Rauch, M., and Tarjan, R.E. [1992]: Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM Journal on Computing 21 (1992), 1184–1192

Edmonds, J. [1967]: Optimum branchings. Journal of Research of the National Bureau of Standards B 71 (1967), 233–240

Edmonds, J. [1970]: Submodular functions, matroids and certain polyhedra. In: Combinatorial Structures and Their Applications; Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications 1969 (R. Guy, H. Hanani, N. Sauer, J. Schönheim, eds.), Gordon and Breach, New York 1970, pp. 69–87

Edmonds, J. [1973]: Edge-disjoint branchings. In: Combinatorial Algorithms (R. Rustin, ed.), Algorithmic Press, New York 1973, pp. 91–96

Fortune, S. [1987]: A sweepline algorithm for Voronoi diagrams. Algorithmica 2 (1987), 153–174

Frank, A. [1981]: On disjoint trees and arborescences. In: Algebraic Methods in Graph Theory; Colloquia Mathematica Societatis János Bolyai 25 (L. Lovász, V.T. Sós, eds.), North-Holland, Amsterdam 1981, pp. 159–169

Frank, A. [1979]: Covering branchings. Acta Scientiarum Mathematicarum (Szeged) 41 (1979), 77–82

Fredman, M.L., and Tarjan, R.E. [1987]: Fibonacci heaps and their uses in improved network optimization problems. Journal of the ACM 34 (1987), 596–615

Fredman, M.L., and Willard, D.E. [1994]: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Journal of Computer and System Sciences 48 (1994), 533–551

Fujishige, S. [2010]: A note on disjoint arborescences. Combinatorica 30 (2010), 247–252

Fulkerson, D.R. [1974]: Packing rooted directed cuts in a weighted directed graph. Mathematical Programming 6 (1974), 1–13

Gabow, H.N. [1995]: A matroid approach to finding edge connectivity and packing arborescences. Journal of Computer and System Sciences 50 (1995), 259–273

Gabow, H.N., Galil, Z., and Spencer, T. [1989]: Efficient implementation of graph algorithms using contraction. Journal of the ACM 36 (1989), 540–572

Gabow, H.N., Galil, Z., Spencer, T., and Tarjan, R.E. [1986]: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6 (1986), 109–122

Gabow, H.N., and Manu, K.S. [1998]: Packing algorithms for arborescences (and spanning trees) in capacitated graphs. Mathematical Programming B 82 (1998), 83–109

Jarník, V. [1930]: O jistém problému minimálním. Práca Moravské Pr̆írodovĕdecké Spolec̆nosti 6 (1930), 57–63

Karger, D., Klein, P.N., and Tarjan, R.E. [1995]: A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM 42 (1995), 321–328

Karp, R.M. [1972]: A simple derivation of Edmonds’ algorithm for optimum branchings. Networks 1 (1972), 265–272

King, V. [1997]: A simpler minimum spanning tree verification algorithm. Algorithmica 18 (1997), 263–270

Knuth, D.E. [1992]: Axioms and hulls; LNCS 606. Springer, Berlin 1992

Korte, B., and Nešetřil, J. [2001]: Vojtĕch Jarník’s work in combinatorial optimization. Discrete Mathematics 235 (2001), 1–17

Kruskal, J.B. [1956]: On the shortest spanning subtree of a graph and the travelling salesman problem. Proceedings of the AMS 7 (1956), 48–50

Lovász, L. [1976]: On two minimax theorems in graph. Journal of Combinatorial Theory B 21 (1976), 96–103

Nash-Williams, C.S.J.A. [1961]: Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society 36 (1961), 445–450

Nash-Williams, C.S.J.A. [1964]: Decompositions of finite graphs into forests. Journal of the London Mathematical Society 39 (1964), 12

Nešetřil, J., Milková, E., and Nešetřilová, H. [2001]: Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history. Discrete Mathematics 233 (2001), 3–36

Pettie, S., and Ramachandran, V. [2002]: An optimal minimum spanning tree algorithm. Journal of the ACM 49 (2002), 16–34

Prim, R.C. [1957]: Shortest connection networks and some generalizations. Bell System Technical Journal 36 (1957), 1389–1401

Prüfer, H. [1918]: Neuer Beweis eines Satzes über Permutationen. Arch. Math. Phys. 27 (1918), 742–744

Shamos, M.I., and Hoey, D. [1975]: Closest-point problems. Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science (1975), 151–162

Sylvester, J.J. [1857]: On the change of systems of independent variables. Quarterly Journal of Mathematics 1 (1857), 42–56

Tarjan, R.E. [1975]: Efficiency of a good but not linear set union algorithm. Journal of the ACM 22 (1975), 215–225

Tutte, W.T. [1961]: On the problem of decomposing a graph into n connected factor. Journal of the London Mathematical Society 36 (1961), 221–230

Zhou, H., Shenoy, N., and Nicholls, W. [2002]: Efficient minimum spanning tree construction without Delaunay triangulation. Information Processing Letters 81 (2002), 271–276

Titel: Spanning Trees and Arborescences
verfasst von: Bernhard Korte
Jens Vygen
Verlag: Springer Berlin Heidelberg
Buch: Combinatorial Optimization
Print ISBN: 978-3-662-56038-9

Electronic ISBN: 978-3-662-56039-6

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-662-56039-6_6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"