Matching theory / by László Lovász and Michael D. Plummer.
Series North-Holland mathematics studies: 121Editor: Budapest : Akadémiai Kiadó, 1986Descripción: xxxiii, 544 p. : ill. ; 25 cmISBN: 9630541688Otra clasificación: 90C10 (05B35 05C70 90C05)Preface vii Basic Terminology xxix 1 Matchings in bipartite graphs 1.0. Introduction [1] 1.1. The Theorems of König, P. Hall and Frobenius [4] Box 1A. NP-properties, good characterizations and minimax theorems [8] 1.2. A bipartite matching algorithm: the Hungarian Method [12] Box 1B. On algorithms [16] 1.3. Deficiency, surplus and a glimpse of matroid theory [17] Box 1C. Matroids [27] 1.4. Some consequences of bipartite matching theorems [29] 2 Flow theory 2.0. Introduction [41] 2.1. The Max-Flow Min-Cut Theorem [42] 2.2. Flow algorithms [46] Box 2A. Searching a graph [53] Box 2B. Numbers in algorithms [59] 2.3. Flow-equivalent trees [61] 2.4. Applications of flow theory to matching theory [68] 2.5. Matchings, flows and measures [74] 3 Size and structure of maximum matchings 3.0. Introduction [83] 3.1. Tutte’s theorem, Gallai’s lemma and Berge’s formula [84] Box 3A. Matching matroids and matroid duality [92] 3.2.The Gallai-Edmonds Structure Theorem [93] 3.3.Toward a calculus of barriers [102] 3.4.Sufficient conditions for matchings of a given size [110] Bipartite graphs with perfect matchings 4.0.Introduction [121] 4.1.Elementary graphs and their ear structure [122] 4.2.Minimal elementary bipartite graphs [127] 4.3.Decomposition into elementary bipartite graphs [137] General graphs with perfect matchings 5.0.Introduction [143] 5.1.Elementary graphs: elementary properties [145] 5.2.The canonical partition P(G) [150] 5.3.Saturated graphs and cathedrals [159] 5.4.Ear structure of 1-extendable graphs [174] 5.5.More about factor-critical and bicritical graphs [195] Somegraph-theoretical problems related to matchings 6.0.Introduction [213] 6.1.2-matchings and 2-covers [213] 6.2.2-bicritical and regularizable graphs [217] 6*3.Matchings, 2-matchings and the Konig Property [220] Box 6A. Reducibility problems and NP-completeness [226] 6.4.Hamilton cycles and 2-matchings [228] 6.5.The Chinese Postman Problem [231] 6.6.Optimum paths, cycles, joins and cuts [243] Box 6B. Packing paths, cycles, joins and cuts [253] 7 Matching and linear programming 7.0. Introduction [255] Box 7A. Cones, polytopes and polyhedra, and other preliminaries from linear programming [256] Box 7B. Linear programming algorithms [261] 7.1. Linear programming and matching in bigraphs [266] Box 7C. The Hoffman-Kruskal Theorem and other conditions of integrality [272] 7.2. Matchings and fractional matchings [273] 7.3. The matching polytope [274] Box 7D. Cutting planes [283] 7.4. Chromatic index [285] Box 7E. Good characterizations other than the Farkas Lemma [290] 7.5. Fractional matching polytopes and cover polyhedra [291] 7.6. The dimension of the perfect matching polytope [292] Box 7F. The dimension of a “good” polytope [303] 8 Determinants and matchings 8.0. Introduction [307] 8.1. Permanents [309] 8.2. The method of variables [315] 8.3. The Pfaffian and the number of perfect matchings [318] 8.4. Probabilistic enumeration of perfect matchings [330] Box 8A. Probabilistic methods in graph theory [331] 8.5. Matching polynomials [333] 8.6. More on the number of perfect matchings [345] 8.7. Two applications to physical science [349] 9 Matching algorithms 9.0. Introduction [357] 9.1. The Edmonds Matching Algorithm [358] 9.2. Weighted matching [369] 9.3. An algorithm based upon the Gallai-Edmonds Theorem [376] 9.4. A linear programming algorithm for matching [379] 10 The f-factor problem 10.0. Introduction [333] 10.1. Reduction principles [385] 10.2. A structure theory for f-factors [388] 10.3. Realization of degree sequences [404] 11 Matroid matching 11.0. Introduction [409] 11.1. Formulations of the Matroid Matching Problem [409] Box 11A. Oracles [413] Box 11B. Minimizing submodular set functions [417] 11.2. The main theorem of polymatroid matching [426] 11.3. Matching in special polymatroids [433] 12 Vertex packing and covering 12.0. Introduction [443] 12.1. Critical graphs [445] 12.2. Vertex packing polytopes [456] 12.3. Hypergraph matching [466] 12.4. Vertex packing in claw-free graphs [471] Box 12A. Bounds on the independence number, or: can anything be done with NP-complete problems? [480] References [483] Index of Terms [527] Index of Symbols [539]
| Item type | Home library | Shelving location | Call number | Materials specified | Status | Date due | Barcode |
|---|---|---|---|---|---|---|---|
Libros
|
Instituto de Matemática, CONICET-UNS | Libros ordenados por tema | 05 L896 (Browse shelf) | Available | A-9225 |
Edición conjunta con North-Holland, Amsterdam, ISBN 0444879161.
Incluye referencias bibliográficas (p. [483]-526) e índice.
Preface vii --
Basic Terminology xxix --
1 Matchings in bipartite graphs --
1.0. Introduction [1] --
1.1. The Theorems of König, P. Hall and Frobenius [4] --
Box 1A. NP-properties, good characterizations and minimax theorems [8] --
1.2. A bipartite matching algorithm: the Hungarian Method [12] --
Box 1B. On algorithms [16] --
1.3. Deficiency, surplus and a glimpse of matroid theory [17] --
Box 1C. Matroids [27] --
1.4. Some consequences of bipartite matching theorems [29] --
2 Flow theory --
2.0. Introduction [41] --
2.1. The Max-Flow Min-Cut Theorem [42] --
2.2. Flow algorithms [46] --
Box 2A. Searching a graph [53] --
Box 2B. Numbers in algorithms [59] --
2.3. Flow-equivalent trees [61] --
2.4. Applications of flow theory to matching theory [68] --
2.5. Matchings, flows and measures [74] --
3 Size and structure of maximum matchings --
3.0. Introduction [83] --
3.1. Tutte’s theorem, Gallai’s lemma and Berge’s formula [84] --
Box 3A. Matching matroids and matroid duality [92] --
3.2.The Gallai-Edmonds Structure Theorem [93] --
3.3.Toward a calculus of barriers [102] --
3.4.Sufficient conditions for matchings of a given size [110] --
Bipartite graphs with perfect matchings --
4.0.Introduction [121] --
4.1.Elementary graphs and their ear structure [122] --
4.2.Minimal elementary bipartite graphs [127] --
4.3.Decomposition into elementary bipartite graphs [137] --
General graphs with perfect matchings --
5.0.Introduction [143] --
5.1.Elementary graphs: elementary properties [145] --
5.2.The canonical partition P(G) [150] --
5.3.Saturated graphs and cathedrals [159] --
5.4.Ear structure of 1-extendable graphs [174] --
5.5.More about factor-critical and bicritical graphs [195] --
Somegraph-theoretical problems related to matchings --
6.0.Introduction [213] --
6.1.2-matchings and 2-covers [213] --
6.2.2-bicritical and regularizable graphs [217] --
6*3.Matchings, 2-matchings and the Konig Property [220] --
Box 6A. Reducibility problems and NP-completeness [226] --
6.4.Hamilton cycles and 2-matchings [228] --
6.5.The Chinese Postman Problem [231] --
6.6.Optimum paths, cycles, joins and cuts [243] --
Box 6B. Packing paths, cycles, joins and cuts [253] --
7 Matching and linear programming --
7.0. Introduction [255] --
Box 7A. Cones, polytopes and polyhedra, and other preliminaries from linear programming [256] --
Box 7B. Linear programming algorithms [261] --
7.1. Linear programming and matching in bigraphs [266] --
Box 7C. The Hoffman-Kruskal Theorem and other conditions --
of integrality [272] --
7.2. Matchings and fractional matchings [273] --
7.3. The matching polytope [274] --
Box 7D. Cutting planes [283] --
7.4. Chromatic index [285] --
Box 7E. Good characterizations other than the --
Farkas Lemma [290] --
7.5. Fractional matching polytopes and cover polyhedra [291] --
7.6. The dimension of the perfect matching polytope [292] --
Box 7F. The dimension of a “good” polytope [303] --
8 Determinants and matchings --
8.0. Introduction [307] --
8.1. Permanents [309] --
8.2. The method of variables [315] --
8.3. The Pfaffian and the number of perfect matchings [318] --
8.4. Probabilistic enumeration of perfect matchings [330] --
Box 8A. Probabilistic methods in graph theory [331] --
8.5. Matching polynomials [333] --
8.6. More on the number of perfect matchings [345] --
8.7. Two applications to physical science [349] --
9 Matching algorithms --
9.0. Introduction [357] --
9.1. The Edmonds Matching Algorithm [358] --
9.2. Weighted matching [369] --
9.3. An algorithm based upon the Gallai-Edmonds Theorem [376] --
9.4. A linear programming algorithm --
for matching [379] --
10 The f-factor problem --
10.0. Introduction [333] --
10.1. Reduction principles [385] --
10.2. A structure theory for f-factors [388] --
10.3. Realization of degree sequences [404] --
11 Matroid matching --
11.0. Introduction [409] --
11.1. Formulations of the Matroid Matching Problem [409] --
Box 11A. Oracles [413] --
Box 11B. Minimizing submodular set functions [417] --
11.2. The main theorem of polymatroid matching [426] --
11.3. Matching in special polymatroids [433] --
12 Vertex packing and covering --
12.0. Introduction [443] --
12.1. Critical graphs [445] --
12.2. Vertex packing polytopes [456] --
12.3. Hypergraph matching [466] --
12.4. Vertex packing in claw-free graphs [471] --
Box 12A. Bounds on the independence number, or: can anything be done with NP-complete problems? [480] --
References [483] --
Index of Terms [527] --
Index of Symbols [539] --
MR, 88b:90087
Click on an image to view it in the image viewer
There are no comments on this title.