Algorithmic Graph Theory

Front Cover
Cambridge University Press, Jun 27, 1985 - Computers - 259 pages
1 Review
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

Other editions - View all

Common terms and phrases

References to this book

All Book Search results »

About the author (1985)

Gibbons, Department of Computer Science, Warwick University.

Bibliographic information