- Membership
- MAA Press
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

Publisher:

Springer

Publication Date:

2009

Number of Pages:

795

Format:

Hardcover

Edition:

2

Series:

Springer Monographs in Mathematics

Price:

149.00

ISBN:

9781848009974

Category:

Monograph

[Reviewed by , on ]

Miklós Bóna

02/19/2009

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

Multigraphs

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

References

Symbol Index

Author Index

Subject Index.

- Log in to post comments