You are here

Graphs, Networks and Algorithms

Dieter Jungnickel
Publisher: 
Springer
Publication Date: 
2008
Number of Pages: 
650
Format: 
Hardcover
Edition: 
3
Series: 
Algorithms and Computation in Mathematics 5
Price: 
89.95
ISBN: 
9783540727798
Category: 
Textbook
[Reviewed by
Francis Fung
, on
01/16/2012
]

Graphs, Networks, and AIgorithms is a comprehensive and up-to-date textbook and reference on graph-theoretical methods in combinatorial optimization, together with fundamentals of graph theory. Combinatorial optimization involves finding an “optimal” object out of a space of such objects, typically maximizing or minimizing some metric (such as cost, distance, or flow), subject to some constraints. The theory has its origins in problems such as finding the most efficient assignment of workers to tasks, or the minimum total required length of cable required to create a network connecting a set of cities. See [S] and [F] for some historical surveys of combinatorial optimization (Interestingly, the assignment problem, which it treated near the end of this book, was one of the first combinatorial optimization problems to be studied.)

Chapter 1 covers graph theory basics, including the characterization of Eulerian graphs, the enumeration of trees via Prüfer codes, planar graphs, and an application to tournament scheduling. Chapter 2 discusses algorithms, data structures, and complexity. The treatment is a bit more abstract than in standard computer science algorithm text books, for example mentioning a “queue” as a data structure useful for breadth-first search but relegating its discussion to a footnote and a reference to a data structures book. It also discusses Hierholzer’s algorithm for detecting Euler tours and how it can be used to construct de Bruijn sequences, as well as a discussion of NP-completeness.

Chapter 3 focuses on shortest path algorithms, introducing breadth-first search and Dijkstra’s algorithm for finding shortest paths, with an application to train schedules. It also introduces path algebras. Chapter 4 covers algorithms for finding minimum length spanning trees, including those of Prim, Kruskal, and Boruvka, as well as Steiner trees (where one is allowed to add vertices to reduce the total length of the tree). References are given for implementations using more efficient data structures (e.g., Fibonacci heaps).

Chapter 5 treats greedy algorithms from the point of view of matroids, and gives bounds for how efficient a greedy algorithm can be (in terms of its “rank quotient”). Chapter 6 covers flows in networks, starting with the Ford-Fulkerson algorithm for finding maximal flows, and then covering the polynomial-time Edmonds-Karp algorithm and several improvements, as well as the Goldberg-Tarjan algorithm.

Chapter 7 applies network flow algorithms to establish several combinatorial results including Menger’s theorem and König’s theorem, Philip Hall’s marriage theorem, Dilworth’s theorem, Baranyai’s theorem, and the Gale-Ryser theorem. Chapter 8 delves deeper into connectivity results. Depth-first search is first introduced here, and then 2-connected graphs are characterized. An efficient DFS-based algorithm for finding strongly connected components is given.

Chapter 9 deals with graph colorings, including Brooks’ theorem, which bounds the number of colors necessary to color the graph’s vertices (its vertex chromatic number) by the maximal degree of a vertex, and Vizing’s theorem, an analogous result for the number of colors needed to color the graph’s edges (its edge chromatic number). It also discusses the colorability of Cayley graphs of groups, and gives a proof of the five-color theorem, as well as some references to the more famous four-color theorem.

Chapter 10 is an extensive chapter on circulations, which are generalizations of flows where the flow condition must hold for all vertices (i.e., without a distinguished source and sink). Circulations are treated using linear algebraic methods. Several algorithms for constructing optimal circulations are established, including those of Klein, Busacker-Gowen, and Goldberg-Tarjan. A final section discusses error-correcting codes derived from graphs.

Chapter 11 treats the network simplex algorithm, an analogue of the simplex algorithm for linear programming. Chapter 12 on synthesis of networks describes how to construct a network that provides a specified set of flows between its vertices (i.e., if we know, for each pair of vertices, how much flow we want between them, which edges do we have to build, and with what capacities?) Chapter 13 treats algorithms for finding perfect matchings in graphs that are not necessarily bipartite, including Edmonds’ algorithm.

Chapter 14 treats weighted matchings in bipartite graphs, particularly the Hungarian algorithm, along with some background in linear programming, a survey without proofs of weighted matchings in arbitrary graphs, a treatment of the Chinese postman problem, and an application to determining shortest paths in undirected graphs. It concludes with a section on decoding graphical codes. The final chapter 15 treats algorithms for hard problems, focusing on the traveling salesman problem, including lower bounds (relaxations and subgradient optimization), approximation algorithms, upper bounds (heuristics and local search), and some techniques for finding optimal solutions (branch and bound). The book concludes with over 80 pages of solutions to the exercises and a detailed list of references.

Overall, the book’s exposition is efficient and the reader is expected to have a firm background in reading and constructing proofs. It has a decidedly practical bent; for example, it only mentions topics such as graph automorphisms, and states Kuratowski’s Theorem on characterizations of planar graphs in Chapter 1 but refers elsewhere for the proof. The author has taken great care to provide worked-out examples to illustrate the algorithms, often running for several pages, as well as complexity estimates (and references to more efficient implementations when available).

Concrete applications are given for the algorithms, e.g., scheduling project tasks by finding longest paths in a digraph, setting up tournament matchings via graph factorizations, and finding optimal connections in a public transport system via Dijkstra’s algorithm. The graph algorithms are expressed using a Pascal-like pseudo-code, and detailed proofs are given for their correctness. In terms of abstraction, the book lies somewhere between graph theory mathematics texts such as Diestel [D] and computer science algorithms texts such as Cormen-Leiserson-Rivest-Stein [CLRS].

A key strength of this book is the extensive references and commentary on extensions, generalizations, and further results, giving the reader copious pointers on where to pursue topics in further depth. The book is written at a level suitable for advanced mathematics or computer science undergraduates (though the author states that the material has been used even with high school students). I give it a very strong recommendation as an advanced and up-to-date text and reference on combinatorial optimization and applied graph theory.

References

[D] Diestel, Reinhard, Graph Theory, 4th. ed., New York: Springer-Verlag, 2010. (Previewable online.)

[F] Frank, András, “On Kuhn’s Hungarian Method - A Tribute from Hungary”, TR-2004-14, Egerváry Research Group on Combinatorial Optimization.

[CLRS] Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein, Introduction to Algorithms, 3rd. ed., Cambridge, MA: The MIT Press, 2009.

[S] Schrijver, Alexander, “On the History of Combinatorial Optimization (til 1960)."


Francis Fung is a software engineer at Google. He can be reached at “fyc”, followed by his last name, at “yahoo” followed by “com”.