Graphs and algorithms

Cover......Page __sk_0000.djvu
Copyright......Page __sk_0002.djvu
Contents......Page __sk_0003.djvu
Preface......Page __sk_0007.djvu
Acknowledgements......Page __sk_0013.djvu
Notation......Page __sk_0015.djvu
1 Generalities about Graphs......Page __sk_0019.djvu
1 Definitions and basic concepts......Page __sk_0020.djvu
2 Matrices associated with graphs......Page __sk_0023.djvu
3 Connectivity......Page __sk_0030.djvu
4 Cycles and cocycles. Cyclomatic number......Page __sk_0039.djvu
5 Some special graphs......Page __sk_0041.djvu
6 Hypergraphs......Page __sk_0048.djvu
7 Random graphs and connectivity......Page __sk_0051.djvu
Exercises......Page __sk_0054.djvu
1 Definitions and examples......Page __sk_0059.djvu
2 Algorithms......Page __sk_0061.djvu
3 The central scheduling problem......Page __sk_0082.djvu
Exercises......Page __sk_0089.djvu
1 An algebra for the shortest path problem......Page __sk_0102.djvu
2 Definitions and properties of path algebras......Page __sk_0104.djvu
3 A few examples......Page __sk_0112.djvu
4 General algorithms......Page __sk_0120.djvu
6 A special dioid......Page __sk_0130.djvu
7 Left dioids and right dioids......Page __sk_0132.djvu
8 Generalized path algebras......Page __sk_0135.djvu
Exercises......Page __sk_0142.djvu
1 Trees. Definitions and properties......Page __sk_0147.djvu
2 The minimum weight spanning tree problem......Page __sk_0153.djvu
3 Arborescences......Page __sk_0159.djvu
Exercises......Page __sk_0168.djvu
5 Flows and Transportation Networks......Page __sk_0178.djvu
1 Definitions and properties......Page __sk_0179.djvu
2 The problem of maximum flow in a transportation network......Page __sk_0184.djvu
3 The problem of compatible flow. Theorem of compatibility......Page __sk_0193.djvu
4 Minimum cost flows......Page __sk_0196.djvu
Exercises......Page __sk_0212.djvu
6 Flows with Gains. Multicommodity Flows......Page __sk_0238.djvu
1 Flows with gains......Page __sk_0239.djvu
2 Multicommodity flows......Page __sk_0261.djvu
Exercises......Page __sk_0281.djvu
7 Matchings and b-matchings......Page __sk_0296.djvu
1 The maximum matching problem......Page __sk_0297.djvu
2 Algorithm to find a maximum matching......Page __sk_0300.djvu
3 Maximum weight matchings......Page __sk_0329.djvu
4 An algorithm for the maximum weight matching problem......Page __sk_0331.djvu
5 b-matchings. Maximum b-matching and b-matching of maximum weight......Page __sk_0339.djvu
Exercises......Page __sk_0342.djvu
8 Eulerian and Hamiltonian Walks......Page __sk_0355.djvu
1 Eulerian cycles and chains......Page __sk_0356.djvu
2 The (non-directed) Chinese postman problem......Page __sk_0358.djvu
3 Hamiltonian cycles and circuits......Page __sk_0362.djvu
Exercises......Page __sk_0376.djvu
9 Matroids......Page __sk_0394.djvu
1 Definitions and fundamental results......Page __sk_0395.djvu
2 Duality......Page __sk_0402.djvu
3 The maximum weight independent subset problem: the greedy algorithm......Page __sk_0407.djvu
4 Intersections of matroids......Page __sk_0414.djvu
5 Matroids with parity conditions and generalizations......Page __sk_0429.djvu
6 Polymatroids......Page __sk_0432.djvu
Exercises......Page __sk_0442.djvu
1 Equivalence between problems......Page __sk_0450.djvu
2 Partitioning and covering problems in a hypergraph......Page __sk_0452.djvu
3 Packing problems (or matching) in a hypergraph......Page __sk_0461.djvu
4 Colouring of a graph and of a hypergraph......Page __sk_0464.djvu
5 The multidimensional knapsack problem......Page __sk_0471.djvu
6 Fixed cost problems and set functions......Page __sk_0477.djvu
7 Scheduling problems......Page __sk_0481.djvu
8 Some other concrete problems......Page __sk_0484.djvu
9 Reductions between problems......Page __sk_0487.djvu
Exercises......Page __sk_0492.djvu
11 Branch and Bound Algorithms......Page __sk_0514.djvu
1 An example of branch and bound......Page __sk_0515.djvu
2 Branch and bound methods......Page __sk_0518.djvu
3 Two examples of applications......Page __sk_0523.djvu
4 Lower bounds and penalties......Page __sk_0533.djvu
5 The ‘ALICE’ computer code (Laurière)......Page __sk_0542.djvu
Exercises......Page __sk_0549.djvu
12 Approximate Algorithms......Page __sk_0570.djvu
1 Iterative algorithms......Page __sk_0571.djvu
2 Greedy algorithms......Page __sk_0576.djvu
3 Regularization of costs......Page __sk_0585.djvu
4 Optimality of the approximate algorithms......Page __sk_0588.djvu
Exercises......Page __sk_0591.djvu
Appendix 1 Linear programming......Page __sk_0605.djvu
Appendix 2 Integer linear programming......Page __sk_0628.djvu
Appendix 3 Lagrangean relaxation and solving the dual problem......Page __sk_0635.djvu
Appendix 4 Dynamic programming......Page __sk_0647.djvu
Appendix 5 Minimum ratio problems......Page __sk_0654.djvu
Index......Page __sk_0661.djvu