## Algorithmic Graph TheoryThis is a textbook on graph theory, especially suitable for computer scientists but also suitable for mathematicians with an interest in computational complexity. Although it introduces most of the classical concepts of pure and applied graph theory (spanning trees, connectivity, genus, colourability, flows in networks, matchings and traversals) and covers many of the major classical theorems, the emphasis is on algorithms and thier complexity: which graph problems have known efficient solutions and which are intractable. For the intractable problems a number of efficient approximation algorithms are included with known performance bounds. Informal use is made of a PASCAL-like programming language to describe the algorithms. A number of exercises and outlines of solutions are included to extend and motivate the material of the text. |

### What people are saying - Write a review

User Review - Flag as inappropriate

karthikeyan

### Contents

Introducing graphs and algorithmic complexity | 1 |

12 Introducing algorithmic complexity | 8 |

13 Introducing data structures and depthfirst searching | 16 |

131 Adjacency matrices and adjacency lists | 17 |

132 Depthfirst searching | 20 |

133 Two lineartime algorithms | 24 |

14 Summary and references | 32 |

Exercises | 33 |

Exercises | 148 |

Eulerian and Hamiltonian tours | 153 |

611 Eulerian graphs | 155 |

6 12 Finding Eulerian circuits | 156 |

62 Postman problems | 161 |

621 Counting Eulerian circuits | 162 |

522 The Chinese postman problem for undirected graphs | 163 |

525 The Chinese postman problem for digraphs | 165 |

Spanningtrees branchings and connectivity | 39 |

211 Optimum weight spanningtrees | 40 |

211 Optimum branchings | 42 |

213 Enumeration of spanningtrees | 49 |

22 Circuits cutsets and connectivity | 54 |

222 Fundamental cutsets of a graph | 57 |

223 Connectivity | 60 |

23 Summary and references | 62 |

Exercises | 63 |

Planar graphs | 67 |

32 Genus crossingnumber and thickness | 71 |

33 Characterisations of planarity | 75 |

331 Dual graphs | 81 |

34 A planarity testing algorithm | 85 |

35 Summary and references | 92 |

Exercises | 93 |

Networks and flows | 96 |

42 Maximising the flow in a network | 98 |

43 Mengers theorems and connectivity | 106 |

44 A minimumcost flow algorithm | 111 |

45 Summary and references | 118 |

Exercises | 120 |

Matchings | 125 |

52 Maximumcardinality matchings | 126 |

521 Perfect matchings | 134 |

53 Maximumweight matchings | 136 |

54 Summary and references | 147 |

63 Hamiltonian tours | 169 |

632 Finding all Hamiltonian tours by matricial products | 173 |

633 The travelling salesman problem | 175 |

634 2factors of a graph | 182 |

64 Summary and references | 184 |

Exercises | 185 |

Colouring graphs | 189 |

72 Colouring graphs | 195 |

722 Vertexcolouring | 198 |

723 Chromatic polynomials | 201 |

73 Facecolourings of embedded graphs | 204 |

752 The fourcolour theorem | 207 |

74 Summary and references | 210 |

Exercises | 212 |

Graph problems and intractability | 216 |

811 The classes P and NP | 217 |

812 NPcompleteness and Cooks theorem | 222 |

82 NPcomplete graph problems | 227 |

822 Problems of Hamiltonian paths and circuits and the travelling salesman problem | 229 |

823 Problems concerning the colouring of graphs | 235 |

83 Concluding comments | 241 |

244 | |

Exercises | 245 |

On linear programming | 249 |

254 | |

256 | |

### Other editions - View all

### Common terms and phrases

adjacency lists algorithm of figure articulation point augmenting path bipartite graph chapter circuit of G clique coloured complete graph computation configurations construct corollary cut-edge cut-set decision problem define degree denote depth-first search described DFI(v digraph digraph G dominating set dual edge incident efficient algorithms end-point Eulerian circuit example exercise exists following theorem free vertex G contains graph G graph theory Hamiltonian circuit Hamiltonian path independent set induction hypothesis instance integer labelled outer lemma linear programming matching algorithm maximise maximum branching maximum-cardinality matching maximum-flow maximum-flow problem maximum-weight matching minimum minimum-weight spanning-tree NDTM number of edges number of vertices obtained odd-degree perfect matching Pk(G planar graph polynomial time algorithm Proof provides pseudo-vertex root satisfied sequence set of edges shortest path simple graph slackness conditions solved spanning out-tree strongly connected component subpath subset travelling salesman problem tree undirected graph variables vertex zero