Half-integral linkages in highly connected directed graphs

DOI10.4230/LIPIcs.ESA.2017.36zbMath1448.05087arXiv1611.01004MaRDI QIDQ5111723

Katherine Edwards, Paul Wollan, Irene Muzi

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1611.01004

zbMATH Keywords

treewidthdirected graphlinkage

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (6)

Constant Congestion Brambles in Directed Graphs ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Half-integral linkages in highly connected directed graphs ⋮ A relaxation of the directed disjoint paths problem: a global congestion metric helps ⋮ A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. ⋮ Digraphs of Bounded Width

Cites Work

• The directed subgraph homeomorphism problem
• 2-linked graphs
• Highly connected non-2-linked digraphs
• Highly connected sets and the excluded grid theorem
• Directed tree-width
• Graph minors. XIII: The disjoint paths problem
• The Directed Grid Theorem
• Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
• An Improved Algorithm for Finding Cycles Through Elements
• Finding k Disjoint Paths in a Directed Planar Graph
• Half-integral linkages in highly connected directed graphs
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem

This page was built for publication: Half-integral linkages in highly connected directed graphs