| Preface | p. xi |
| Introducing graphs and algorithmic complexity | p. 1 |
| Introducing graphs | p. 1 |
| Introducing algorithmic complexity | p. 8 |
| Introducing data structures and depth-first searching | p. 16 |
| Adjacency matrices and adjacency lists | p. 17 |
| Depth-first searching | p. 20 |
| Two linear-time algorithms | p. 24 |
| Summary and references | p. 32 |
| Exercises | p. 33 |
| Spanning-trees, branchings and connectivity | p. 39 |
| Spanning-trees and branchings | p. 39 |
| Optimum weight spanning-trees | p. 40 |
| Optimum branchings | p. 42 |
| Enumeration of spanning-trees | p. 49 |
| Circuits, cut-sets and connectivity | p. 54 |
| Fundamental circuits of a graph | p. 54 |
| Fundamental cut-sets of a graph | p. 57 |
| Connectivity | p. 60 |
| Summary and references | p. 62 |
| Exercises | p. 63 |
| Planar graphs | p. 67 |
| Basic properties of planar graphs | p. 67 |
| Genus, crossing-number and thickness | p. 71 |
| Characterisations of planarity | p. 75 |
| Dual graphs | p. 81 |
| A planarity testing algorithm | p. 85 |
| Summary and references | p. 92 |
| Exercises | p. 93 |
| Networks and flows | p. 96 |
| Networks and flows | p. 96 |
| Maximising the flow in a network | p. 98 |
| Menger's theorems and connectivity | p. 106 |
| A minimum-cost flow algorithm | p. 111 |
| Summary and references | p. 118 |
| Exercises | p. 120 |
| Matchings | p. 125 |
| Definitions | p. 125 |
| Maximum-cardinality matchings | p. 126 |
| Perfect matchings | p. 134 |
| Maximum-weight matchings | p. 136 |
| Summary and references | p. 147 |
| Exercises | p. 148 |
| Eulerian and Hamiltonian tours | p. 153 |
| Eulerian paths and circuits | p. 153 |
| Eulerian graphs | p. 155 |
| Finding Eulerian circuits | p. 156 |
| Postman problems | p. 161 |
| Counting Eulerian circuits | p. 162 |
| The Chinese postman problem for undirected graphs | p. 163 |
| The Chinese postman problem for digraphs | p. 165 |
| Hamiltonian tours | p. 169 |
| Some elementary existence theorems | p. 169 |
| Finding all Hamiltonian tours by matricial products | p. 173 |
| The travelling salesman problem | p. 175 |
| 2-factors of a graph | p. 182 |
| Summary and references | p. 184 |
| Exercises | p. 185 |
| Colouring graphs | p. 189 |
| Dominating sets, independence and cliques | p. 189 |
| Colouring graphs | p. 195 |
| Edge-colouring | p. 195 |
| Vertex-colouring | p. 198 |
| Chromatic polynomials | p. 201 |
| Face-colourings of embedded graphs | p. 204 |
| The five-colour theorem | p. 204 |
| The four-colour theorem | p. 207 |
| Summary and references | p. 210 |
| Exercises | p. 212 |
| Graph problems and intractability | p. 217 |
| Introduction to NP-completeness | p. 217 |
| The classes P and NP | p. 217 |
| NP-completeness and Cook's theorem | p. 222 |
| NP-complete graph problems | p. 227 |
| Problems of vertex cover, independent set and clique | p. 227 |
| Problems of Hamiltonian paths and circuits and the travelling salesman problem | p. 229 |
| Problems concerning the colouring of graphs | p. 235 |
| Concluding comments | p. 241 |
| Summary and references | p. 244 |
| Exercises | p. 245 |
| On linear programming | p. 249 |
| Author index | p. 254 |
| Subject index | p. 256 |
| Table of Contents provided by Syndetics. All Rights Reserved. |
