Opis

Presents a number of algorithms, and includes chapters devoted to topics such as branchings, feedback arc and vertex sets, connectivity augmentations, sparse subdigraphs with prescribed connectivity. This book focuses on applications which include quantum mechanics, bioinformatics, embedded computing, and the travelling salesman problem.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.