Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

12.  b-Matchings and T-Joins

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
loading …

Abstract

In this chapter we introduce two more combinatorial optimization problems, the MAXIMUM WEIGHT b -MATCHING PROBLEM in Section 12.1 and the MINIMUM WEIGHT T -JOIN PROBLEM in Section 12.2. Both can be regarded as generalizations of the MINIMUM WEIGHT PERFECT MATCHING PROBLEM and also include other important problems.

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 Weighted Matching
Nächstes Kapitel Matroids
Literatur
Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., and Schrijver, A. [1998]: Combinatorial Optimization. Wiley, New York 1998, Sections 5.4 and 5.5
Frank, A. [1996]: A survey on T-joins, T-cuts, and conservative weightings. In: Combinatorics, Paul Erdős is Eighty; Volume 2 (D. Miklós, V.T. Sós, T. Szőnyi, eds.), Bolyai Society, Budapest 1996, pp. 213–252
Gerards, A.M.H. [1995]: Matching. 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. 135–224
Lovász, L., and Plummer, M.D. [1986]: Matching Theory. Akadémiai Kiadó, Budapest 1986, and North-Holland, Amsterdam 1986
Schrijver, A. [1983]: Min-max results in combinatorial optimization; Section 6. In: Mathematical Programming; The State of the Art – Bonn 1982 (A. Bachem, M. Grötschel, B. Korte, eds.), Springer, Berlin 1983, pp. 439–500
Schrijver, A. [2003]: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin 2003, Chapters 29–33
Anstee, R.P. [1987]: A polynomial algorithm for b-matchings: an alternative approach. Information Processing Letters 24 (1987), 153–157
Babenko, M.A. and Karzanov, A.V. [2009]: Minimum mean cycle problem in bidirected and skew-symmetric graphs. Discrete Optimization 6 (2009), 92–97
Barahona, F. [1993]: Reducing matching to polynomial size linear programming. SIAM Journal on Optimization 3 (1993), 688–695
Caprara, A., and Fischetti, M. [1996]: \(\{0, \frac{1} {2}\}\)-Chvátal-Gomory cuts. Mathematical Programming 74 (1996), 221–235
Edmonds, J. [1965]: Maximum matching and a polyhedron with (0,1) vertices. Journal of Research of the National Bureau of Standards B 69 (1965), 125–130
Edmonds, J., and Johnson, E.L. [1970]: Matching: A well-solved class of integer linear programs. 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., and Johnson, E.L. [1973]: Matching, Euler tours and the Chinese postman. Mathematical Programming 5 (1973), 88–124
Gabow, H.N. [1983]: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. Proceedings of the 15th Annual ACM Symposium on Theory of Computing (1983), 448–456
Goldberg, A.V., and Karzanov, A.V. [2004]: Maximum skew-symmetric flows and matchings. Mathematical Programming A 100 (2004), 537–568
Guan, M. [1962]: Graphic programming using odd and even points. Chinese Mathematics 1 (1962), 273–277
Hadlock, F. [1975]: Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing 4 (1975), 221–225
Karzanov, A.V. [1985]: Minimum mean weight cuts and cycles in directed graphs. In: Kachestvennye i Priblizhennye Metody Issledovaniya Operatornykh Uravneniĭ (V.S. Klimov, ed.), Yaroslavl State University Press, Yaroslavl 1985, pp. 72–83 [in Russian]. English translation: American Mathematical Society Translations Ser. 2, Vol. 158 (1994), 47–55
Karzanov, A.V. [1986]: An algorithm for determining a maximum packing of odd-terminus cuts and its applications. In: Isslidovaniya po Prikladnoĭ Teorii Grafov (A.S. Alekseev, ed.), Nauka Siberian Dept., Novosibirsk, 1986, pp. 126–140 [in Russian]. English translation: American Mathematical Society Translations Ser. 2, Vol. 158 (1994), 57–70
Letchford, A.N., Reinelt, G., and Theis, D.O. [2008]: Odd minimum cut sets and b-matchings revisited. SIAM Journal on Discrete Mathematics 22 (2008), 1480–1487
Marsh, A.B. [1979]: Matching algorithms. Ph.D. thesis, Johns Hopkins University, Baltimore 1979
Padberg, M.W., and Rao, M.R. [1982]: Odd minimum cut-sets and b-matchings. Mathematics of Operations Research 7 (1982), 67–80
Pulleyblank, W.R. [1973]: Faces of matching polyhedra. Ph.D. thesis, University of Waterloo, 1973
Pulleyblank, W.R. [1980]: Dual integrality in b-matching problems. Mathematical Programming Study 12 (1980), 176–196
Rizzi, R. [2002]: Minimum T-cuts and optimal T-pairings. Discrete Mathematics 257 (2002), 177–181
Rothvoß, T. [2017]: The matching polytope has exponential extension complexity. Journal of the ACM 64 (2017), Article 41
Sebő, A. [1987]: A quick proof of Seymour’s theorem on T-joins. Discrete Mathematics 64 (1987), 101–103
Seymour, P.D. [1981]: On odd cuts and multicommodity flows. Proceedings of the London Mathematical Society (3) 42 (1981), 178–192
Tutte, W.T. [1952]: The factors of graphs. Canadian Journal of Mathematics 4 (1952), 314–328
Tutte, W.T. [1954]: A short proof of the factor theorem for finite graphs. Canadian Journal of Mathematics 6 (1954), 347–352
Yannakakis, M. [1991]: Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences 43 (1991), 441–466
Metadaten
Titel
b-Matchings and T-Joins
verfasst von
Bernhard Korte
Jens Vygen
Copyright-Jahr
2018
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_12