Graph theory. An algorithmic approach.

*(English)*Zbl 0321.94011
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.]

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 |