Digraphs

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.