Skip to content

Algorithmic Graph Theory

ISBN-10: 0521288819

ISBN-13: 9780521288811

Edition: 1985

Authors: Alan Gibbons

List price: $59.99
Shipping box This item qualifies for FREE shipping.
Blue ribbon 30 day, 100% satisfaction guarantee!
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

Description:

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.
Customers also bought

Book details

List price: $59.99
Copyright year: 1985
Publisher: Cambridge University Press
Publication date: 6/27/1985
Binding: Paperback
Pages: 272
Size: 6.25" wide x 9.25" long x 0.75" tall
Weight: 0.836
Language: English

Alan Gibbons is a full-time writer and a visiting speaker and lecturer at schools, colleges and literary events nationwide, including the major book festivals: Edinburgh, Northern Children's Book Festival, Swansea, Cheltenham, Sheffield and Salford. Alan has recently embarked on a high-profile, nationwide campaign to champion libraries and librarianship and to reevaluate government commitment to educational spending. He lives in Liverpool with his wife and four children. Visit his website at http://www.alangibbons.com, read his blog at http://alangibbons.net, follow him on Twitter at https://twitter.com/mygibbo, Facebook at https://www.facebook.com/alan.gibbons.35 and Flickr at http://www.flickr.com/people/71279646@N08.

Preface
Introducing graphs and algorithmic complexity
Introducing graphs
Introducing algorithmic complexity
Introducing data structures and depth-first searching
Adjacency matrices and adjacency lists
Depth-first searching
Two linear-time algorithms
Summary and references
Exercises
Spanning-trees, branchings and connectivity
Spanning-trees and branchings
Optimum weight spanning-trees
Optimum branchings
Enumeration of spanning-trees
Circuits, cut-sets and connectivity
Fundamental circuits of a graph
Fundamental cut-sets of a graph
Connectivity
Summary and references
Exercises
Planar graphs
Basic properties of planar graphs
Genus, crossing-number and thickness
Characterisations of planarity
Dual graphs
A planarity testing algorithm
Summary and references
Exercises
Networks and flows
Networks and flows
Maximising the flow in a network
Menger's theorems and connectivity
A minimum-cost flow algorithm
Summary and references
Exercises
Matchings
Definitions
Maximum-cardinality matchings
Perfect matchings
Maximum-weight matchings
Summary and references
Exercises
Eulerian and Hamiltonian tours
Eulerian paths and circuits
Eulerian graphs
Finding Eulerian circuits
Postman problems
Counting Eulerian circuits
The Chinese postman problem for undirected graphs
The Chinese postman problem for digraphs
Hamiltonian tours
Some elementary existence theorems
Finding all Hamiltonian tours by matricial products
The travelling salesman problem
2-factors of a graph
Summary and references
Exercises
Colouring graphs
Dominating sets, independence and cliques
Colouring graphs
Edge-colouring
Vertex-colouring
Chromatic polynomials
Face-colourings of embedded graphs
The five-colour theorem
The four-colour theorem
Summary and references
Exercises
Graph problems and intractability
Introduction to NP-completeness
The classes P and NP
NP-completeness and Cook's theorem
NP-complete graph problems
Problems of vertex cover, independent set and clique
Problems of Hamiltonian paths and circuits and the travelling salesman problem
Problems concerning the colouring of graphs
Concluding comments
Summary and references
Exercises
On linear programming
Author index
Subject index