Classes of directed graphs. ([2018])

• Record Type: Book
• Further Information: Note: Jørgen Bang-Jensen, Gregory Gutin, editors.
• Editors: Bang-Jensen, Jørgen, 1960-; Gutin, Gregory, 1957-
• Contents: Intro; Preface; Highlights; Technical Remarks; Acknowledgements; Contents; 1. Basic Terminology, Notation and Results; 1.1 Sets, Matrices, Vectors and Hypergraphs; 1.2 Digraphs, Subgraphs, Neighbours, Degrees; 1.3 Walks, Trails, Paths, Cycles and Path-Cycle Subgraphs; 1.4 Isomorphism and Basic Operations on Digraphs; 1.5 Strong Connectivity; 1.6 Linkages; 1.7 Undirected Graphs and Orientations of Undirected and Directed Graphs; 1.8 Trees in Digraphs; 1.9 Flows in Networks; 1.10 Polynomial and Exponential Time Algorithms, SAT and ETH; 1.11 Parameterized Algorithms and Complexity. 1.12 Approximation Algorithms2. Tournaments and Semicomplete Digraphs; 2.1 Special Tournaments; 2.2 Basic Properties of Tournaments and Semicomplete Digraphs; 2.2.1 Median Orders, a Powerful Tool; 2.2.2 Kings; 2.2.3 Scores and Landau's Theorem; 2.3 Spanning k-Strong Subtournaments of Semicomplete Digraphs; 2.4 The Second Neighbourhood Conjecture; 2.4.1 Fisher's Original Proof; 2.4.2 Proof Using Median Orders; 2.4.3 Relation with Other Conjectures; 2.5 Disjoint Paths and Cycles; 2.5.1 Polynomial Algorithms for Linkage and Weak Linkage. 2.5.2 Sufficient Conditions for a Tournament to be k-Linked2.5.3 The Bermond-Thomassen Conjecture for Tournaments; 2.6 Hamiltonian Paths and Cycles; 2.6.1 Redei's Theorem; 2.6.2 Hamiltonian Connectivity; 2.6.3 Hamiltonian Cycles Containing or Avoiding Prescribed Arcs; 2.7 Oriented Subgraphs of Tournaments; 2.7.1 Transitive Subtournaments; 2.7.2 Oriented Paths in Tournaments; 2.7.3 Oriented Cycles in Tournaments; 2.7.4 Trees in Tournaments; 2.7.5 Largest n-Unavoidable Digraphs; 2.7.6 Generalization to k-Chromatic Digraphs; 2.8 Vertex-Partitions of Semicomplete Digraphs. 2.8.1 2-Partitions into Strong Semicomplete Digraphs2.8.2 Partition into Highly Strong Subtournaments; 2.8.3 2-Partitions With Prescribed Minimum Degrees; 2.8.4 2-Partitions with Restrictions Both Inside and Between Sets; 2.8.5 Partitioning into Transitive Tournaments; 2.9 Feedback Sets; 2.9.1 Feedback Vertex Sets; 2.9.2 Feedback Arc Sets; 2.9.3 FPT Algorithms for Feedback vertex set in tournaments; 2.9.4 FPT Algorithms for Feedback arc set in tournaments; 2.10 Small Certicates for k-(Arc)-Strong Connectivity; 2.11 Increasing Connectivity by Adding or Reversing Arcs. 2.12 Arc-Disjoint Spanning Subdigraphs of Semicomplete Digraphs2.12.1 Arc-Disjoint Hamiltonian Paths and Cycles; 2.12.2 Arc-Disjoint Spanning Strong Subdigraphs; 2.12.3 Arc-Disjoint In- and Out-Branchings; 2.13 Minors of Semicomplete Digraphs; 2.14 Miscellaneous Topics; 2.14.1 Arc-Pancyclicity; 2.14.2 Critically k-Strong Tournaments; 2.14.3 Subdivisions and Linkages; 3. Acyclic Digraphs; 3.1 Acyclic Orderings and Longest and Shortest Paths; 3.2 Transitive Acyclic Digraphs; 3.3 Out-branchings and in-branchings; 3.3.1 Extremal number of leaves; 3.3.2 Bounded out-degrees.
• Publisher Details: Cham : Springer
• Publication Date: 2018
• Copyright Date: 2018
• Extent: 1 online resource
• Subjects: 511/.54; Mathematics; Directed graphs; MATHEMATICS -- General; Directed graphs; Computers -- Data Processing; Computers -- Programming -- Algorithms; Discrete mathematics; Algorithms & data structures; Computational complexity; Computer software; Mathematics -- Graphic Methods; Combinatorics & graph theory; Electronic books
• Languages: English
• ISBNs: 9783319718408; 3319718401
• Related ISBNs: 9783319718392; 3319718398
• Notes: Note: Includes bibliographical references and index.; Note: Online resource; title from PDF title page (EBSCO, viewed June 22, 2018).
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.