+612 9045 4394
Algorithmic Graph Theory - Alan Gibbons

Algorithmic Graph Theory

Paperback Published: 26th August 1985
ISBN: 9780521288811
Number Of Pages: 272

Share This Book:


Ships in 10 to 15 business days

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 their 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.

Industry Reviews

'... the book covers a relatively large part of algorithmic graph theory. The theory presented is well motivated. I can conclude that the textbook is well written and for those interested in learning algorithmic graph theory, this is s good introduction.' Zentralblatt fur Mathematik und ihre Grenzgebiete '... this is a stimulating book for those who want to learn some basic algorithms of graph theory and who already know where to apply them ... nice and thorough introduction.' European Journal of Operational Research 'Alan Gibbons' book ... succeeds admirably.' The Times Higher Education Supplement

Prefacep. xi
Introducing graphs and algorithmic complexityp. 1
Introducing graphsp. 1
Introducing algorithmic complexityp. 8
Introducing data structures and depth-first searchingp. 16
Adjacency matrices and adjacency listsp. 17
Depth-first searchingp. 20
Two linear-time algorithmsp. 24
Summary and referencesp. 32
Exercisesp. 33
Spanning-trees, branchings and connectivityp. 39
Spanning-trees and branchingsp. 39
Optimum weight spanning-treesp. 40
Optimum branchingsp. 42
Enumeration of spanning-treesp. 49
Circuits, cut-sets and connectivityp. 54
Fundamental circuits of a graphp. 54
Fundamental cut-sets of a graphp. 57
Connectivityp. 60
Summary and referencesp. 62
Exercisesp. 63
Planar graphsp. 67
Basic properties of planar graphsp. 67
Genus, crossing-number and thicknessp. 71
Characterisations of planarityp. 75
Dual graphsp. 81
A planarity testing algorithmp. 85
Summary and referencesp. 92
Exercisesp. 93
Networks and flowsp. 96
Networks and flowsp. 96
Maximising the flow in a networkp. 98
Menger's theorems and connectivityp. 106
A minimum-cost flow algorithmp. 111
Summary and referencesp. 118
Exercisesp. 120
Matchingsp. 125
Definitionsp. 125
Maximum-cardinality matchingsp. 126
Perfect matchingsp. 134
Maximum-weight matchingsp. 136
Summary and referencesp. 147
Exercisesp. 148
Eulerian and Hamiltonian toursp. 153
Eulerian paths and circuitsp. 153
Eulerian graphsp. 155
Finding Eulerian circuitsp. 156
Postman problemsp. 161
Counting Eulerian circuitsp. 162
The Chinese postman problem for undirected graphsp. 163
The Chinese postman problem for digraphsp. 165
Hamiltonian toursp. 169
Some elementary existence theoremsp. 169
Finding all Hamiltonian tours by matricial productsp. 173
The travelling salesman problemp. 175
2-factors of a graphp. 182
Summary and referencesp. 184
Exercisesp. 185
Colouring graphsp. 189
Dominating sets, independence and cliquesp. 189
Colouring graphsp. 195
Edge-colouringp. 195
Vertex-colouringp. 198
Chromatic polynomialsp. 201
Face-colourings of embedded graphsp. 204
The five-colour theoremp. 204
The four-colour theoremp. 207
Summary and referencesp. 210
Exercisesp. 212
Graph problems and intractabilityp. 217
Introduction to NP-completenessp. 217
The classes P and NPp. 217
NP-completeness and Cook's theoremp. 222
NP-complete graph problemsp. 227
Problems of vertex cover, independent set and cliquep. 227
Problems of Hamiltonian paths and circuits and the travelling salesman problemp. 229
Problems concerning the colouring of graphsp. 235
Concluding commentsp. 241
Summary and referencesp. 244
Exercisesp. 245
On linear programmingp. 249
Author indexp. 254
Subject indexp. 256
Table of Contents provided by Syndetics. All Rights Reserved.

ISBN: 9780521288811
ISBN-10: 0521288819
Audience: Tertiary; University or College
Format: Paperback
Language: English
Number Of Pages: 272
Published: 26th August 1985
Country of Publication: GB
Dimensions (cm): 23.06 x 15.49  x 1.75
Weight (kg): 0.42