# Algorithmic Graph Theory

Cambridge University Press, Jun 27, 1985 - Computers - 259 pages
This 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 84 Summary and references 244 Exercises 245 On linear programming 249 Author index 254 Subject index 256 Copyright