Digraphs : Theory, Algorithms and Applications

by Bang-Jensen, Jorgen; Gutin, Gregory

• ISBN13: 9781852332686
• ISBN10: 1852332689
• eBook ISBN(s): 9781447138860
• Format: Hardcover
• Copyright: 2000-12-01
• Publisher: Springer Verlag
• More Book Details
• Purchase Benefits

Summary

The study of directed graphs has developed enormously over recent decades, yet no book covers more than a tiny fraction of the results from more than 3000 research articles on the topic. Digraphsis the first book to present a unified and comprehensive survey of the subject. In addition to covering the theoretical aspects, including detailed proofs of many important results, the authors present a number of algorithms and applications. The applications of digraphs and their generalizations include among other things recent developments in the Travelling Salesman Problem, genetics and network connectivity. More than 700 exercises and 180 figures will help readers to study the topic while open problems and conjectures will inspire further research. This book will be essential reading and reference for all graduate students, researchers and professionals in mathematics, operational research, computer science and other areas who are interested in graph theory and its applications.

Author Biography

Jorgen Bang-Jensen is associate 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

Table of Contents

Basic Terminology, Natation and Results	1	(44)
Sets, Subsets, Matrices and Vectors	1	(1)
Digraphs, Subdigraphs, Neighbours, Degrees	2	(4)
Isomorphism and Basic Operations on Digraphs	6	(4)
Walks, Trails, Paths, Cycles and Path-Cycle Subdigraphs	10	(6)
Strong and Unilateral Connectivity	16	(2)
Undirected Graphs, Biorientations and Orientations	18	(4)
Mixed Graphs and Hypergraphs	22	(3)
Classes of Directed and Undirected Graphs	25	(3)
Algorithmic Aspects	28	(7)
Algorithms and their Complexity	29	(4)
NP-Complete and NP-Hard Problems	33	(2)
Application: Solving the 2-Satisfiability Problem	35	(3)
Exercises	38	(7)
Distances	45	(50)
Terminology and Notation on Distances	46	(2)
Structure of Shortest Paths	48	(2)
Algorithms for Finding Distances in Digraphs	50	(9)
Breadth-First Search (BFS)	50	(2)
Acyclic Digraphs	52	(1)
Dijkstra's Algorithm	53	(2)
The Bellman-Ford-Moore Algorithm	55	(3)
The Floyd-Warshall Algorithm	58	(1)
Inequalities Between Radius, Out-Radius and Diameter	59	(2)
Radius and Diameter of a Strong Digraph	59	(1)
Extreme Values of Out-Radius and Diameter	60	(1)
Maximum Finite Diameter of Orientations	61	(2)
Minimum Diameter of Orientations of Multigraphs	63	(4)
Minimum Diameter Orientations of Complete Multipartite Graphs	67	(2)
Minimum Diameter Orientations of Extensions of Graphs	69	(2)
Minimum Diameter Orientations of Cartesian Products of Graphs	71	(3)
Kings in Digraphs	74	(4)
2-Kings in Tournaments	74	(1)
Kings in Semicomplete Multipartite Digraphs	75	(3)
Kings in Generalizations of Tournaments	78	(1)
Application: The One-Way Street and the Gossip Problems	78	(4)
The One-Way Street Problem and Orientations of Digraphs	79	(1)
The Gossip Problem	80	(2)
Application: Exponential Neighbourhood Local Search for the TSP	82	(7)
Local Search for the TSP	82	(2)
Linear Time Searchable Exponential Neighbourhoods for the TSP	84	(1)
The Assignment Neighbourhoods	85	(1)
Diameters of Neighbourhood Structure Digraphs for the TSP	86	(3)
Exercises	89	(6)
Flows in Networks	95	(76)
Definitions and Basic Properties	95	(4)
Flows and Their Balance Vectors	96	(2)
The Residual Network	98	(1)
Reductions Among Different Flow Models	99	(5)
Eliminating Lower Bounds	99	(1)
Flows with one Source and one Sink	100	(1)
Circulations	101	(1)
Networks with Bounds and Costs on the Vertices	102	(2)
Flow Decompositions	104	(1)
Working with the Residual Network	105	(3)
The Maximum Flow Problem	108	(6)
The Ford-Fulkerson Algorithm	110	(3)
Maximum Flows and Linear Programming	113	(1)
Polynomial Algorithms for Finding a Maximum (s,t)-Flow	114	(8)
Flow Augmentations Along Shortest Augmenting Paths	114	(2)
Blocking Flows in Layered Networks and Dinic's Algorithm	116	(1)
The Preflow-Push Algorithm	117	(5)
Unit Capacity Networks and Simple Networks	122	(3)
Unit Capacity Networks	122	(2)
Simple Networks	124	(1)
Circulations and Feasible Flows	125	(2)
Minimum Value Feasible (s,t)-Flows	127	(1)
Minimum Cost Flows	128	(9)
Characterizing Minimum Cost Flows	131	(3)
Building up an Optimal Solution	134	(3)
Applications of Flows	137	(10)
Maximum Matchings in Bipartite Graphs	137	(4)
The Directed Chinese Postman Problem	141	(1)
Finding Subdigraphs with Prescribed Degrees	142	(1)
Path-Cycle Factors in Directed Multigraphs	143	(2)
Cycle Subdigraphs Covering Specified Vertices	145	(2)
The Assignment Problem and the Transportation Problem	147	(11)
Exercises	158	(13)
Classes of Digraphs	171	(56)
Depth-First Search	172	(3)
Acyclic Orderings of the Vertices in Acyclic Digraphs	175	(1)
Transitive Digraphs, Transitive Closures and Reductions	176	(3)
Strong Digraphs	179	(3)
Line Digraphs	182	(5)
The de Bruijn and Kautz Digraphs and their Generalizations	187	(4)
Series-Parallel Digraphs	191	(4)
Quasi-Transitive Digraphs	195	(3)
The Path-Merging Property and Path-Mergeable Digraphs	198	(2)
Locally In-Semicomplete and Locally Out-Semicomplete Digraphs	200	(2)
Locally Semicomplete Digraphs	202	(13)
Round Digraphs	203	(4)
Non-Strong Locally Semicomplete Digraphs	207	(2)
Strong Round Decomposable Locally Semicomplete Digraphs	209	(2)
Classification of Locally Semicomplete Digraphs	211	(4)
Totally φi-Decomposable Digraphs	215	(2)
Intersection Digraphs	217	(2)
Planar Digraphs	219	(2)
Application: Gaussian Elimination	221	(3)
Exercises	224	(3)
Hamiltonicity and Related Problems	227	(54)
Necessary Conditions for Hamiltonicity of Digraphs	229	(5)
Path-Contraction	229	(1)
Quasi-Hamiltonicity	230	(2)
Pseudo-Hamiltonicity and 1-Quasi-Hamiltonicity	232	(1)
Algorithms for Pseudo- and Quasi-Hamiltonicity	233	(1)
Path Covering Number	234	(1)
Path Factors of Acyclic Digraphs with Applications	235	(2)
Hamilton Paths and Cycles in Path-Mergeable Digraphs	237	(1)
Hamilton Paths and Cycles in Locally In-Semicomplete Digraphs	238	(2)
Hamilton Cycles and Paths in Degree-Constrained Digraphs	240	(10)
Sufficient Conditions	240	(6)
The Multi-Insertion Technique	246	(2)
Proofs of Theorems 5.6.1 and 5.6.5	248	(2)
Longest Paths and Cycles in Semicomplete Multipartite Digraphs	250	(14)
Basic Results	251	(2)
The Good Cycle Factor Theorem	253	(3)
Consequences of Lemma 5.7.12	256	(3)
Yeo's Irreducible Cycle Subdigraph Theorem and its Applications	259	(5)
Longest Paths and Cycles in Extended Locally Semicomplete Digraphs	264	(1)
Hamilton Paths and Cycles in Quasi-Transitive Digraphs	265	(4)
Vertex-Heaviest Paths and Cycles in Quasi-Transitive Digraphs	269	(4)
Hamilton Paths and Cycles in Various Classes of Digraphs	273	(3)
Exercises	276	(5)
Hamiltonian Refinements	281	(64)
Hamiltonian Paths with a Prescribed End-Vertex	282	(2)
Weakly Hamiltonian-Connected Digraphs	284	(8)
Results for Extended Tournaments	284	(5)
Results for Locally Semicomplete Digraphs	289	(3)
Hamiltonian-Connected Digraphs	292	(3)
Finding a Hamiltonian (x,y)-Path in a Semicomplete Digraph	295	(4)
Pancyclicity of Digraphs	299	(10)
(Vertex-) Pancyclicity in Degree-Constrained Digraphs	299	(1)
Pancyclicity in Extended Semicomplete and Quasi-Transitive Digraphs	300	(3)
Pancyclic and Vertex-Pancyclic Locally Semicomplete Digraphs	303	(3)
Further Pancyclicity Results	306	(2)
Cycle Extendability in Digraphs	308	(1)
Arc-Pancyclicity	309	(3)
Hamiltonian Cycles Containing or Avoiding Prescribed Arcs	312	(6)
Hamiltonian Cycles Containing Prescribed Arcs	312	(3)
Avoiding Prescribed Arcs with a Hamiltonian Cycle	315	(2)
Hamiltonian Cycles Avoiding Arcs in 2-Cycles	317	(1)
Arc-Disjoint Hamiltonian Paths and Cycles	318	(3)
Oriented Hamiltonian Paths and Cycles	321	(5)
Covering All Vertices of a Digraph by Few Cycles	326	(5)
Cycle Factors with a Fixed Number of Cycles	326	(3)
The Effect of α(D) on Spanning Configurations of Paths and Cycles	329	(2)
Minimum Strong Spanning Subdigraphs	331	(6)
A Lower Bound for General Digraphs	331	(1)
The MSSS Problem for Extended Semicomplete Digraphs	332	(2)
The MSSS Problem for Quasi-Transitive Digraphs	334	(1)
The MSSS Problem for Decomposable Digraphs	335	(2)
Application: Domination Number of TSP Heuristics	337	(2)
Exercises	339	(6)
Global Connectivity	345	(70)
Additional Notation and Preliminaries	346	(3)
The Network Representation of a Directed Multigraph	348	(1)
Ear Decompositions	349	(4)
Menger's Theorem	353	(2)
Application: Determining Arc-and Vertex-Strong Connectivity	355	(3)
The Splitting off Operation	358	(4)
Increasing the Arc-Strong Connectivity Optimally	362	(5)
Increasing the Vertex-Strong Connectivity Optimally	367	(9)
One-Way Pairs	368	(2)
Optimal k-Strong Augmentation	370	(1)
Special Classes of Digraphs	371	(2)
Splittings Preserving k-Strong Connectivity	373	(3)
A Generalization of Arc-Strong Connectivity	376	(2)
Arc Reversals and Vertex-Strong Connectivity	378	(3)
Minimally k-(Arc)-Strong Directed Multigraphs	381	(10)
Minimally k-Arc-Strong Directed Multigraphs	382	(5)
Minimally k-Strong Digraphs	387	(4)
Critically k-Strong Digraphs	391	(1)
Arc-Strong Connectivity and Minimum Degree	392	(1)
Connectivity Properties of Special Classes of Digraphs	393	(2)
Highly Connected Orientations of Digraphs	395	(5)
Packing Cuts	400	(4)
Application: Small Certificates for k-(Arc)-Strong Connectivity	404	(5)
Finding Small Certificates for Strong Connectivity	405	(1)
Finding k-Strong Certificates for k > 1	406	(2)
Certificates for k-Arc-Strong Connectivity	408	(1)
Exercises	409	(6)
Orientations of Graphs	415	(60)
Underlying Graphs of Various Classes of Digraphs	415	(14)
Underlying Graphs of Transitive and Quasi-Transitive Digraphs	416	(3)
Underlying Graphs of Locally Semicomplete Digraphs	419	(2)
Local Tournament Orientations of Proper Circular Arc Graphs	421	(3)
Underlying Graphs of Locally In-Semicomplete Digraphs	424	(5)
Fast Recognition of Locally Semicomplete Digraphs	429	(3)
Orientations With no Even Cycles	432	(3)
Colourings and Orientations of Graphs	435	(2)
Orientations and Nowhere Zero Integer Flows	437	(6)
Orientations Achieving High Arc-Strong Connectivity	443	(3)
Orientations Respecting Degree Constraints	446	(5)
Orientations with Prescribed Degree Sequences	446	(4)
Restrictions on Subsets of Vertices	450	(1)
Submodular Flows	451	(11)
Submodular Flow Models	452	(1)
Existence of Feasible Submodular Flows	453	(4)
Minimum Cost Submodular Flows	457	(1)
Applications of Submodular Flows	458	(4)
Orientations of Mixed Graphs	462	(5)
Exercises	467	(8)
Disjoint Paths and Trees	475	(70)
Additional Definitions	476	(1)
Disjoint Path Problems	477	(10)
The Complexity of the k-Path Problem	478	(4)
Sufficient Conditions for a Digraph to be k-Linked	482	(2)
The k-Path Problem for Acyclic Digraphs	484	(3)
Linkings in Tournaments and Generalizations of Tournaments	487	(10)
Sufficient Conditions in Terms of (Local-) Connectivity	488	(4)
The 2-Path Problem for Semicomplete Digraphs	492	(1)
The 2-Path Problem for Generalizations of Tournaments	493	(4)
Linkings in Planar Digraphs	497	(3)
Arc-Disjoint Branchings	500	(6)
Implications of Edmonds' Branching Theorem	503	(3)
Edge-Disjoint Mixed Branchings	506	(1)
Arc-Disjoint Path Problems	507	(13)
Arc-Disjoint Paths in Acyclic Directed Multigraphs	510	(1)
Arc-Disjoint Paths in Eulerian Directed Multigraphs	511	(6)
Arc-Disjoint Paths in Tournaments and Generalizations of Tournaments	517	(3)
Integer Multicommodity Flows	520	(2)
Arc-Disjoint In-and Out-Branchings	522	(5)
Minimum Cost Branchings	527	(9)
Matroid Intersection Formulation	527	(1)
An Algorithm for a Generalization of the Min Cost Branching Problem	528	(7)
The Minimum Covering Arborescence Problem	535	(1)
Increasing Rooted Arc-Strong Connectivity by Adding New Arcs	536	(2)
Exercises	538	(7)
Cycle Structure of Digraphs	545	(46)
Vector Spaces of Digraphs	546	(3)
Polynomial Algorithms for Paths and Cycles	549	(4)
Disjoint Cycles and Feedback Sets	553	(8)
Complexity of the Disjoint Cycle and Feedback Set Problems	553	(1)
Disjoint Cycles in Digraphs with Minimum Out-Degree at Least k	554	(3)
Feedback Sets and Linear Orderings in Digraphs	557	(4)
Disjoint Cycles Versus Feedback Sets	561	(4)
Relations Between Parameters vi and Ti	561	(2)
Solution of Younger's Conjecture	563	(2)
Application: The Period of Markov Chains	565	(2)
Cycles of Length k Modulo p	567	(6)
Complexity of the Existence of Cycles of Length k Modulo p Problems	568	(2)
Sufficient Conditions for the Existence of Cycles of Length k Modulo p	570	(3)
`Short' Cycles in Semicomplete Multipartite Digraphs	573	(4)
Cycles Versus Paths in Semicomplete Multipartite Digraphs	577	(3)
Girth	580	(3)
Additional Topics on Cycles	583	(3)
Chords of Cycles	583	(1)
Adam's Conjecture	584	(2)
Exercises	586	(5)
Generalizations of Digraphs	591	(48)
Properly Coloured Trails in Edge-Coloured Multigraphs	592	(28)
Properly Coloured Euler Trails	594	(3)
Properly Coloured Cycles	597	(4)
Connectivity of Edge-Coloured Multigraphs	601	(3)
Alternating Cycles in 2-Edge-Coloured Bipartite Multigraphs	604	(3)
Longest Alternating Paths and Cycles in 2-Edge-Coloured Complete Multigraphs	607	(6)
Properly Coloured Hamiltonian Paths in c-Edge-Coloured Complete Graphs, c ⪈ 3	613	(2)
Properly Coloured Hamiltonian Cycles in c-Edge-Coloured Complete Graphs, c ⪈ 3	615	(5)
Arc-Coloured Directed Multigraphs	620	(7)
Complexity of the Alternating Directed Cycle Problem	621	(3)
The Functions f(n) and g(n)	624	(2)
Weakly Eulerian Arc-Coloured Directed Multigraphs	626	(1)
Hypertournaments	627	(5)
Out-Degree Sequences of Hypertournaments	628	(1)
Hamilton Paths	629	(1)
Hamilton Cycles	630	(2)
Application: Alternating Hamilton Cycles in Genetics	632	(4)
Proof of Theorem 11.4.1	634	(1)
Proof of Theorem 11.4.2	635	(1)
Exercises	636	(3)
Additional Topics	639	(44)
Seymour's Second Neighbourhood Conjecture	639	(3)
Ordering the Vertices of a Digraph of Paired Comparisons	642	(8)
Paired Comparison Digraphs	642	(3)
The Kano-Sakamoto Methods of Ordering	645	(1)
Orderings for Semicomplete PCDs	645	(1)
The Mutual Orderings	646	(1)
Complexity and Algorithms for Forward and Backward Orderings	647	(3)
(k, l)-Kernels	650	(4)
Kernels	650	(3)
Quasi-Kernels	653	(1)
List Edge-Colourings of Complete Bipartite Graphs	654	(4)
Homomorphisms-A Generalization of Colourings	658	(6)
Other Measures of Independence in Digraphs	664	(1)
Matroids	665	(8)
The Dual of a Matroid	667	(1)
The Greedy Algorithm for Matroids	668	(1)
Independence Oracles	669	(1)
Union of Matroids	670	(1)
Two Matroid Intersection	671	(1)
Intersections of Three or More Matroids	672	(1)
Finding Good Solutions of NP-Hard Problems	673	(4)
Exercises	677	(6)
References	683	(34)
Symbol Index	717	(6)
Author Index	723	(8)
Subject Index	731