You are here

Digraphs: Theory, Algorithms and Applications

Jǿrgen Bang-Jensen and Gregory Gutin
Publication Date: 
Number of Pages: 
Springer Monographs in Mathematics
[Reviewed by
Miklós Bóna
, on

This is a very comprehensive volume on directed graphs and related topics. It consists of 18 chapters (compared to 12 for the first edition) and almost 800 pages. This reviewer will not attempt to list the contents — prospective readers can find that in the link above. Instead, he will discuss a few characteristics of this impressive, well-conceived, and well-written book, and its possible uses.

First, the book is an excellent reference. The authors understand that even in 800 pages it would be impossible to cover everything about digraphs in a self-contained fashion, so they were not afraid to make some choices. They chose to be comprehensive, at the expense of being self-contained. This means that there is an unusually high number of results in the book that are not proved; but they are there, their place in the theory is discussed, and interested readers are given references for their proofs. You can be reasonably certain that if the result you are looking for is not proved in the book, the book will at least help you find it.

Second, for the reason given in the previous paragraph, this reviewer would not use the book for a regular, lecture-based, course, but rather for a series of seminars, where each student would be responsible for presenting a part of the material, including proofs that are in the book and proofs that are not in the book.

Third, unlike in a large number of research monographs, the authors do an excellent job putting their topic into context. Hence the book will be useful not just for researchers focusing on digraphs, but also for everyone else for whom digraphs are tools, and not goals. The applications discussed in the book are not limited to topics where digraphs are a necessity, such as networks. They include problems like Konig's theorem and Philip Hall's theorem, that may be proved by using digraphs, but may also be proved without using digraphs. This commendable approach will extend the reach of the book.

Last, but not least, an extensive list of conjectures and open questions is included in every chapter. These are typically very well presented and easy to understand. I am not taking a big risk when I predict that with the help of books like this, the area will continue to progress at a fast pace.

Miklós Bóna is associate professor of mathematics at the University of Florida.

1. Basic Terminology, Notation and Results
1.1 Sets, Matrices and Vectors
1.2 Digraphs, Subdigraphs, Neighbours, Degrees
1.3 Isomorphism and Basic Operations on Digraphs
1.4 Walks, Trails, Paths, Cycles and Path-Cycle Subdigraphs
1.5 Strong and Unilateral Connectivity
1.6 Undirected Graphs, Biorientations and Orientations
1.7 Trees and Euler Trails in Digraphs
1.8 Mixed Graphs, Orientations of Digraphs, and Hypergraphs
1.9 Depth-First Search
1.10 Exercises

2. Classes of Digraphs
2.1 Acyclic Digraphs
2.2 Multipartite Digraphs and Extended Digraphs
2.3 Transitive Digraphs, Transitive Closures and Reductions
2.4 Line Digraphs
2.5 The de Bruijn and Kautz Digraphs
2.6 Series-Parallel Digraphs
2.7 Quasi-Transitive Digraphs
2.8 Path-Mergeable Digraphs
2.9 Locally In/Out-Semicomplete Digraphs
2.10 Locally Semicomplete Digraphs
2.11 Totally F-Decomposable Digraphs
2.12 Planar Digraphs
2.13 Digraphs of Bounded Tree-Width
2.14 Other Families of Digraphs
2.15 Exercises

3. Distances
3.1 Terminology and Notation on Distances
3.2 Structure of Shortest Paths
3.3 Algorithms for Finding Distances in Digraphs
3.3.1 Breadth-First Search (BFS)
3.3.2 Acyclic Digraphs
3.3.3 Dijkstra’s Algorithm
3.3.4 The Bellman-Ford-Moore Algorithm
3.3.5 The Floyd-Warshall Algorithm
3.4 Inequalities on Diameter
3.5 Minimum Diameter of Orientations of Multigraphs
3.6 Minimum Diameter Orientations of Some Graphs and Digraphs
3.7 Kings in Digraphs
3.8 (k, l)-Kernels
3.9 Exercises

4. Flows in Networks
4.1 Definitions and Basic Properties
4.2 Reductions Among Different Flow Models
4.3 Flow Decompositions
4.4 Working with the Residual Network
4.5 The Maximum Flow Problem
4.6 Polynomial Algorithms for Finding a Maximum (s, t)-Flow
4.7 Unit Capacity Networks and Simple Networks
4.8 Circulations and Feasible Flows
4.9 Minimum Value Feasible (s, t)-Flows
4.10 Minimum Cost Flows
4.11 Applications of Flows
4.12 Exercises

5. Connectivity of Digraphs
5.1 Additional Notation and Preliminaries
5.2 Finding the Strong Components of a Digraph
5.3 Ear Decompositions
5.4 Menger’s Theorem
5.5 Determining Arc- and Vertex-Strong Connectivity
5.6 Minimally k-(Arc)-Strong Directed Multigraphs
5.7 Critically k-Strong Digraphs
5.8 Connectivity Properties of Special Classes of Digraphs
5.9 Disjoint X-paths in Digraphs
5.10 Exercises

6. Hamiltonian, Longest and Vertex-Cheapest Paths and Cycles
6.1 Complexity
6.2 Hamilton Paths and Cycles in Path-Mergeable Digraphs
6.3 Hamilton Paths and Cycles in Locally In-Semicomplete Digraphs
6.4 Hamilton Cycles and Paths in Degree-Constrained Digraphs
6.5 Longest Paths and Cycles in Degree-Constrained Oriented Graphs
6.6 Longest Paths and Cycles in Semicomplete Multipartite Digraphs
6.7 Hamilton Paths and Cycles in Quasi-Transitive Digraphs
6.8 Vertex-Cheapest Paths and Cycles
6.9 Hamilton Paths and Cycles in Various Classes of Digraphs
6.10 Exercises

7. Restricted Hamiltonian Paths and Cycles
7.1 Hamiltonian Paths with a Prescribed End-Vertex
7.2 Weakly Hamiltonian-Connected Digraphs
7.3 Hamiltonian-Connected Digraphs
7.4 Hamiltonian Cycles Containing or Avoiding Prescribed Arcs
7.5 Arc-Traceable Digraphs
7.6 Oriented Hamiltonian Paths and Cycles
7.7 Exercises

8. Paths and Cycles of Prescribed Lengths
8.1 Pancyclicity of Digraphs
8.2 Colour Coding: Efficient Algorithms for Paths and Cycles
8.3 Cycles of Length k Modulo p
8.4 Girth
8.5 Short Cycles in Semicomplete Multipartite Digraphs
8.6 Exercises

9. Branchings
9.1 Tutte’s Matrix Tree Theorem
9.2 Optimum Branchings
9.3 Arc-Disjoint Branchings
9.4 Implications of Edmonds’ Branching Theorem
9.5 Out-Branchings with Degree Bounds
9.6 Arc-Disjoint In- and Out-Branchings
9.7 Out-Branchings with Extremal Number of Leaves
9.8 The Source Location Problem
9.9 Miscellaneous Topics
9.10 Exercises

10. Linkages in Digraphs
10.1 Additional Definitions and Preliminaries
10.2 The Complexity of the k-linkage Problem
10.3 Sufficient Conditions for a Digraph to be k-Linked
10.4 The k-linkage Problem for Acyclic Digraphs
10.5 Linkages in (Generalizations of) Tournaments
10.6 Linkages in Planar Digraphs
10.7 Weak Linkages
10.8 Linkages in Digraphs With Large Minimum Out-Degree
10.9 Miscellaneous Topics
10.10 Exercises

11. Orientations of Graphs and Digraphs
11.1 Underlying Graphs of Various Classes of Digraphs
11.2 Orientations With no Even Cycles
11.3 Colourings and Orientations of Graphs
11.4 Orientations and Nowhere Zero Integer Flows
11.5 Orientations Achieving High Arc-Strong Connectivity
11.6 k-Strong Orientations
11.7 Orientations Respecting Degree Constraints
11.8 Submodular Flows
11.9 Orientations of Mixed Multigraphs
11.10 k-(Arc)-Strong Orientations of Digraphs
11.11 Miscellaneous Topics
11.12 Exercises

12. Sparse Subdigraphs with Prescribed Connectivity
12.1 Minimum Strong Spanning Subdigraphs
12.2 Polynomially Solvable Cases of the MSSS problem
12.3 Approximation Algorithms for the MSSS problem
12.4 Small Certificates for k-(Arc)-Strong Connectivity
12.5 Minimum Weight Strong Spanning Subdigraphs. 12.6 Directed Steiner Problems
12.7 Miscellaneous Topics
12.8 Exercises

13. Packings, Coverings and Decompositions
13.1 Packing Directed Cuts: The Lucchesi-Younger Theorem
13.2 Packing Dijoins: Woodall’s Conjecture
13.3 Packing Cycles
13.4 Arc-Disjoint Hamiltonian Paths and Cycles
13.5 Path Factors
13.6 Cycle Factors with the Minimum Number of Cycles
13.7 Cycle Factors with a Fixed Number of Cycles
13.8 Cycle Subdigraphs Covering Specified Vertices
13.9 Proof of Gallai’s Conjecture
13.10 Decomposing a Tournament into Strong Spanning Subdigraphs
13.11 The Directed Path-Partition Conjecture
13.12 Miscellaneous Topics
13.13 Exercises

14. Increasing Connectivity
14.1 The Splitting off Operation
14.2 Increasing the Arc-Strong Connectivity Optimally
14.3 Increasing the Vertex-Strong Connectivity Optimally
14.4 Arc Reversals and Vertex-Strong Connectivity
14.5 Arc-Reversals and Arc-Strong Connectivity
14.6 Increasing Connectivity by Deorienting Arcs
14.7 Miscellaneous topics
14.8 Exercises

15. Feedback Sets and Vertex Orderings
15.1 Two Conjectures on Feedback Arc Sets
15.2 Optimal Orderings in Tournaments
15.3 Complexity of the Feedback Set Problems
15.4 Disjoint Cycles Versus Feedback Sets
15.5 Optimal Orderings and Seymour’s Second Neighbourhood Conjecture
15.6 Adam’s Conjecture
15.7 Exercises

16. Generalizations of Digraphs: Edge-Coloured Multigraphs
16.1 Terminology, Notation and Initial Observations
16.2 Properly Coloured Euler Trails
16.3 Properly Coloured Cycles
16.4 Gadget Graphs and Shortest PC Cycles and (s, t)-Paths
16.5 Long PC Cycles and Paths
16.6 Connectivity of Edge-Coloured Multigraphs
16.7 Alternating Cycles in 2-Edge-Coloured Bipartite Multigraphs
16.8 Alternating Paths and Cycles in 2-Edge-Coloured Complete
16.9 PC Paths and Cycles in c-Edge-Coloured Complete Graphs, c = 3
16.10 Exercises

17. Applications of Digraphs and Edge-Coloured Graphs
17.1 A Digraph Model in Quantum Mechanics
17.2 Embedded Computing and Convex Sets in Acyclic Digraphs
17.3 When Greedy-Like Algorithms Fail
17.4 Domination Analysis of ATSP Heuristics
17.5 Solving the 2-Satisfiability Problem
17.6 Alternating Hamilton Cycles in Genetics
17.7 Gaussian Elimination
17.8 Markov Chains
17.9 List Edge-Colourings
17.10 Digraph Models of Bartering
17.11 PERT/CPM in Project Scheduling
17.12 Finite Automata
17.13 Puzzles and Digraphs
17.14 Gossip Problems
17.15 Deadlocks of Computer Processes
17.16 Exercises

18. Algorithms and their Complexity
18.1 Combinatorial Algorithms
18.2 NP-Complete and NP-Hard Problems
18.3 The Satisfiability Problem
18.4 Fixed-Parameter Tractability and Intractability
18.5 Exponential Algorithms
18.6 Approximation Algorithms
18.7 Heuristics and Meta-heuristics
18.8 Matroids
18.9 Exercises


Symbol Index

Author Index

Subject Index.