Graph theory. An algorithmic approach. (English) Zbl 0321.94011

Christofides, Nicos

Computer Science and Applied Mathematics. New York-London-San Francisco: Academic Press, a subsidiary of Harcourt Brace Jovanovich, Publishers. xv, 400 p. $ 32.25 (1975).

The book contains a comprehensive list of basic graph theoretical algorithms. It is intended to those working in computer science, operations research, electrical and transport engineering, economy, sociology and - last but not least - to mathematicians who are interested in applicable parts of pure mathematics. The book consists of 12 relatively self-contained chapters. In the first chapter, the reader can find all needed concepts, to relate them to his own field. Each of the other chapters contains introduction, definitions, theorems, proofs, descriptions of algorithms, computational aspects, computational results, applications, problems and a lot of references.
Contents: Reachability and connectivity (reaching matrices, calculation of components) - Independence and dominating sets, the set covering problem – Graph colouring (exact and approximate colouring algorithms) - The location of centres – The location of medians – Trees (the shortest spanning tree, the Steiner problem) – Shortest paths – Circuits, cut-sets and Euler’s problem (the cyclomatic number and fundamental circuits, cut-sets, circuit and cut-set matrices, Eulerian circuits and the Chinese postman’s problem) – Hamiltonian circuits, paths and the traveling salesman problem (comparison of methods for finding Hamiltonian circuits, the traveling salesman, shortest spanning tree and assignment problems) – Network flows – Matchings, transportation and assignment problems.
[A Russian translation was published in 1978 by Mir Publ. Moscow under the name Kristofides.]

Reviewer: Jan Reiterman (Praha)

MSC:

05-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
90-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
94-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory
05C85	Graph algorithms (graph-theoretic aspects)
94C05	Analytic circuit theory
94C15	Applications of graph theory to circuits and networks
05C35	Extremal problems in graph theory
05C15	Coloring of graphs and hypergraphs
90B10	Deterministic network models in operations research
68W99	Algorithms in computer science
05C90	Applications of graph theory