Algorithmic graph theory.

*(English)*Zbl 0568.05001
Cambridge etc.: Cambridge University Press. XII, 259 p. hbk: £27.50; $ 47.50; pbk: £8.95; $ 17,95 (1985).

This is a textbook on algorithmic graph theory. From the preface: ”It is intended to be an introductory text for undergraduates or for new postgraduate students. Prerequisites for an understanding of the text have been kept to a minimum.” The book is aimed primarily at computer scientists but it is also suitable for mathematicians and engineers with an interest in computational complexity. Although it introduces most of the classical concepts of pure graph theory and covers many of the main classical theorems, the emphasis is on algorithms and their complexity: which graph problems have known efficient (polynomial) algorithms and which are intractable (NP-complete). Algorithms are described in a PASCAL-like programming language.

The basic text is divided into 8 chapters. Chapter 1 has 38 pages and its title is: Introducing graphs and algorithmic complexity. It includes: efficient representations of graphs, depth-first searching, finding blocks of a graph and finding strong components of a digraph. Chapter 2 (28 p.): Spanning trees, branchings and connecitvity (Prim’s algorithm, Edmonds’ algorithm, enumeration of spanning trees, cut sets, blocks). Chapter 3 (29 p.): Planar graphs (Euler’s formula, Kuratowski’s theorem, dual graphs, the planarity algorithm of Demoucron et al.). Chapter 4 (29 p.): Networks and flows (the Ford-Fulkerson and Edmonds-Karp algorithms, Menger’s theorem, testing connectivity, a minimum-cost flow algorithm). Chapter 5 (28 p.): Matchings (finding a maximum cardinality matching, Tutte’s theorem on perfect matchings, finding a maximum-weight matching). Chapter 6 (36 p.): Eulerian and Hamiltonian tours (characterizing Eulerian graphs or digraphs, finding Eulerian circuits, counting Eulerian circuits, the Chinese postman problems for graphs and digraphs, a few classical results on Hamiltonian graphs, finding all Hamiltonian tours of a graph or digraph by matricial products, the traveling salesman problem: 2-approximation and 3/2-approximation heuristics, 2-factors of a graph). Chapter 7 (28 p.): Coloring graphs (dominating sets, independence and cliques, Turán’s theorem, edge coloring, Vizing’s theorem, vertex- coloring, Brooks’ theorem, chromatic polynomials, face-coloring, the five-color theorem, on the four-color theorem). Chapter 8 (32 p.): Graph problems and intractability (the classes P and NP, Cook’s theorem, NP- complete graph problems: vertex cover, independent set, clique, Hamiltonian paths and circuits, the traveling salesman problem, 3-vertex- coloring of planar graphs, 3-edge-coloring of 3-regular graphs). At the end of each chapter there is a list of references (10-22 items), a brief summary and 10-16 exercises with outlines of solutions. The exercises often extend or motivate the material of the text. The book ends with an appendix on linear programming (4 p.), author index (117 names) and subject index (4 p.).

Although some basic notions (e.g. the NP-hardness) and problems (e.g. the isomorphism problem) are not introduced, 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 a good introduction.

The basic text is divided into 8 chapters. Chapter 1 has 38 pages and its title is: Introducing graphs and algorithmic complexity. It includes: efficient representations of graphs, depth-first searching, finding blocks of a graph and finding strong components of a digraph. Chapter 2 (28 p.): Spanning trees, branchings and connecitvity (Prim’s algorithm, Edmonds’ algorithm, enumeration of spanning trees, cut sets, blocks). Chapter 3 (29 p.): Planar graphs (Euler’s formula, Kuratowski’s theorem, dual graphs, the planarity algorithm of Demoucron et al.). Chapter 4 (29 p.): Networks and flows (the Ford-Fulkerson and Edmonds-Karp algorithms, Menger’s theorem, testing connectivity, a minimum-cost flow algorithm). Chapter 5 (28 p.): Matchings (finding a maximum cardinality matching, Tutte’s theorem on perfect matchings, finding a maximum-weight matching). Chapter 6 (36 p.): Eulerian and Hamiltonian tours (characterizing Eulerian graphs or digraphs, finding Eulerian circuits, counting Eulerian circuits, the Chinese postman problems for graphs and digraphs, a few classical results on Hamiltonian graphs, finding all Hamiltonian tours of a graph or digraph by matricial products, the traveling salesman problem: 2-approximation and 3/2-approximation heuristics, 2-factors of a graph). Chapter 7 (28 p.): Coloring graphs (dominating sets, independence and cliques, Turán’s theorem, edge coloring, Vizing’s theorem, vertex- coloring, Brooks’ theorem, chromatic polynomials, face-coloring, the five-color theorem, on the four-color theorem). Chapter 8 (32 p.): Graph problems and intractability (the classes P and NP, Cook’s theorem, NP- complete graph problems: vertex cover, independent set, clique, Hamiltonian paths and circuits, the traveling salesman problem, 3-vertex- coloring of planar graphs, 3-edge-coloring of 3-regular graphs). At the end of each chapter there is a list of references (10-22 items), a brief summary and 10-16 exercises with outlines of solutions. The exercises often extend or motivate the material of the text. The book ends with an appendix on linear programming (4 p.), author index (117 names) and subject index (4 p.).

Although some basic notions (e.g. the NP-hardness) and problems (e.g. the isomorphism problem) are not introduced, 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 a good introduction.

Reviewer: J.Plesník