Anonymous
Posted May 10, 2001
Digraphs: Theory, Algorithms and Applications by Joergen Bang Jensen and Gregory Gutin Springer-Verlag, London Springer Monographs in Mathematics ISBN 1-85233-268-9 October 2000 754 pages; 186 figures; 705 exercises This book reflects the main achievements of the last three decades in the directed graphs theory as well as many applications including combinatorial optimization, operations research and the fascinating area of mathematics and computer science called discrete mathematics. Since the monograph contents are given in www.imada.sdu.dk/Research/Digraphs/ , I do not wish to go into details of material presented there. Instead I'd like to discuss the aims of the book as well as who could be its readers. The text strives to accomplish the following objectives: 1. To give a great deal of information on both results and proof techniques for specialists in graph theory. No other book covers even 10\% of material provided in Digraphs, and thus before this monograph has been published even specialists in graph theory very often needed to search for a specific result or proof technique through the ocean of literature on digraphs. Now the situation has drastically improved. 2. To introduce researchers and practitioners from various other fields in mathematics, computer science, operations research, biology, etc. to basic and more advanced results in digraph theory and algorithms and some carefully selected applications. It offers much more than merely a pure bibliography and provides the ideal starting point for any researcher who needs to become familiar either with theory oriented aspects of this interesting area or with some application in a relatively short time. 3. To provide enough material for intermediate and final year BSc or MSc courses for students in mathematics, computer science and operations research. The large number of exercises (more than 700) of various difficulty is of great help to instructors and lecturers. The applications provided in the book will help to provide enough motivation for the students to study digraph theory and algorithms. 4. To provide a large variety of topics for final year student projects in mathematics, computer science, operations research and other fields. The monograph can be used as a source for the projects because because several areas of digraph theory are covered there in real depth and they vary from relatively simple to reasonably complicated ones. To summarize, I'd like to notice that the monograph is aimed to a wide range of readers including specialists in mathematics, operations research, computer science, biology, etc. as well as students of second year and higher. Boris Goldengorin, Department of Econometrics and Operations Research, University of Groningen, The Netherlands
Was this review helpful? Yes NoThank you for your feedback. Report this reviewThank you, this review has been flagged.
More About This Textbook
Overview
The theory of directed graphs has developed enormously over recent decades, yet this book (first published in 2000) remains the only book to cover more than a small fraction of the results. New research in the field has made a second edition a necessity.
Substantially revised, reorganised and updated, the book now comprises eighteen chapters, carefully arranged in a straightforward and logical manner, with many new results and open problems.
As well as covering the theoretical aspects of the subject, with detailed proofs of many important results, the authors present a number of algorithms, and whole chapters are devoted to topics such as branchings, feedback arc and vertex sets, connectivity augmentations, sparse subdigraphs with prescribed connectivity, and also packing, covering and decompositions of digraphs. Throughout the book, there is a strong focus on applications which include quantum mechanics, bioinformatics, embedded computing, and the travelling salesman problem.
Detailed indices and topic-oriented chapters ease navigation, and more than 650 exercises, 170 figures and 150 open problems are included to help immerse the reader in all aspects of the subject.
Digraphs is an essential, comprehensive reference for undergraduate and graduate students, and researchers in mathematics, operations research and computer science. It will also prove invaluable to specialists in related areas, such as meteorology, physics and computational biology.
Jørgen Bang-Jensen is a Professor in the Department of Mathematics and Computer Science at the University of Southern Denmark, Odense, Denmark.
Gregory Gutin is Professor of Computer Science at Royal Holloway College, University of London, UK.
Product Details
Related Subjects
Table of Contents
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.