Koha online

From reviews:
“.... The book is a first class textbook and seems to be indispensable for everybody who has to teach combinatorial optimization. It is very helpful for students, teachers, and researchers in this area. The author finds a striking synthesis of nice and interesting mathematical results and practical applications. ... the author pays much attention to the inclusion of well-chosen exercises. The reader does not remain helpless; solutions or at least hints are given in the appendix. Except for some small basic mathematical and algorithmic knowledge the book is self-contained.” (K. Engel, Mathematical Reviews (2002)
Table of Contents
Preface
1. Basic Graph Theory 1.1 Graphs, Subgraphs and Factors 1.2 Paths, Cycles, Connectedness, Trees 1.3 Euler Tours 1.4 Hamiltonian Cycles 1.5 Planar Graphs 1.6 Digraphs1. 7 An Application: Tournaments and Leagues
2. Algorithms and Complexity 2.1 Algorithms 2.2 Representing Graphs 2.3 The Algorithm of Hierholzer 2.4 How to Write Down Algorithms 2.5 The Complexity of Algorithms 2.6 Directed Acyclic Graphs 2.7 NP-Complete Problems 2.8 HC is NP-Complete
3. Shortest Paths 3.1 Shortest Paths 3.2 Finite Metric Spaces 3.3 Breadth First Search and Bipartite Graphs 3.4 Bellman's Equations and Acyclic Digraphs 3.5 An Application: Scheduling Projects 3.6 The Algorithm of Dijkstra 3.7 An Application: Train Schedules 3.8 The Algorithm of Floyd-Warshall 3.9 Cycles of Negative Length 3.10 Path Algebras X Table of Contents
4. Spanning Trees 4.1 Trees and Forests 4.2 Incidence Matrices 4.3 Minimal Spanning Trees 4.4 The Algorithms of Prim, Kruskal and Boruvka 4.5 Maximal Spanning Trees 4.6 Steiner Trees 4.7 Spanning Trees with Restrictions 4.8 Arborescences and Directed Euler Tours
5. The Greedy Algorithm 5.1 The Greedy Algorithm and Matroids 5.2 Characterizations of Matroids 5.3 Duality of Matroids 5.4 The Greedy Algorithm as a Technique for Approximation 5.5 Minimization in Independence Systems 5.6 Accessible Set Systems
6. Flows 6.1 The Theorems of Ford and Fulkerson 6.2 The Algorithm of Edmonds and Karp 6.3 Layered Networks and Phases 6.4 Constructing Blocking Flows 6.5 Zero-One Flows 6.6 The Algorithm of Goldberg and Tarjan
7. Applications in Combinatorics 7.1 Disjoint Paths: The Theorem of Menger 7.2 Matchings: The Theorem of Konig 7.3 Partial Transversals: The Marriage Theorem 7.4 Combinatorics of Matrices 7.5 Dissections: The Theorem of Dilworth7.6 Parallelisms: The Theorem of Baranyai 7.7 Supply and Demand: The Theorem of Gale and Ryser
8. Colourings 8.1 Comparability Graphs and Interval Graphs 8.2 Colourings 8.3 Edge Colourings 8.4 Cayley Graphs
9. Circulations 9.1 Circulations and Flows 9.2 Feasible Circulations 9.3 Elementary Circulations Table of Contents XI 9.4 Minty's Painting Lemma 9.5 The Algorithm of Klein 9.6 The Algorithm of Busacker and Gowen 9.7 Potentials and [-Optimality 9.8 Determining Optimal Circulations by Successive Approximation 9.9 A Polynomial Procedure REFINE 9.10 The Algorithm of Klein II 9.11 Some Further Problems
10. Synthesis of Networks 10.1 Symmetric Networks 10.2 Synthesis of Equivalent Flow Trees 10.3 Synthesizing Minimal Networks 10.4 Cut Trees 10.5 Increasing the Capacities
11. Connectivity 1l.1 k-Connected Graphs for k :::: 2 11.2 Depth First Search 11.3 2-Connected Graphs 11.4 Depth First Search for Directed Graphs 1l.5 Strongly Connected Directed Graphs 1l.6 Edge Connectivity
12. Matchings 12.1 The I-Factor Theorem 12.2 Augmenting Paths 12.3 Alternating Trees and Flowers 12.4 The Algorithm of Edmonds 12.5 Matching Matroids
13. Weighted Matchings 13.1 The Bipartite Case 13.2 The Hungarian Algorithm 13.3 Matchings, Linear Programs and Polytopes 13.4 The General Case 13.5 The Chinese Postman 13.6 Matchings and Shortest Paths 13.7 Further Problems Concerning Matchings
14. A Hard Problem: The TSP 14.1 The Problem 14.2 Lower Bounds: Relaxations A. The Assignment Relaxation XII Table of Contents B. The MST Relaxation C. The I-Tree Relaxation D. The LP Relaxation 14.3 Lower Bounds: Subgradient Optimization 14.4 Algorithms for Approximation 14.5 Upper Bounds: Heuristics 14.6 Upper Bounds: Post-Optimization 14.7 Exact Neighbourhoods 14.8 Optimal Solutions: Branch and Bound 14.9 Concluding Remarks 14.10 Appendix: Some NP-Complete Problems
A. Solutions A.l Solutions for Chapter 1 A.2 Solutions for Chapter 2 A.3 Solutions for Chapter 3 A.4 Solutions for Chapter 4 A.5 Solutions for Chapter 5 A.6 Solutions for Chapter 6 A.7 Solutions for Chapter 7 A.8 Solutions for Chapter 8 A.9 Solutions for Chapter 9 A.lO Solutions for Chapter 10 A.11 Solutions for Chapter 11 A.12 Solutions for Chapter 12 A.13 Solutions for Chapter 13 A.14 Solutions for Chapter 14
B. List of Symbols B.l General Symbols B.2 Special Symbols
References Index