Packing directed circuits quarter-integrally

DOI10.4230/LIPICS.ESA.2019.72MaRDI QIDQ5075819FDOQ5075819

Authors: Tomáš Masařík, Irene Muzi, Marcin Pilipczuk, Paweł Rzążewski, Manuel Sorge 

Publication date: 11 May 2022

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

Recommendations

• Packing directed cycles through a specified vertex set
• Packing directed circuits through prescribed vertices bounded fractionally
• Packing directed circuits
• Packing directed circuits fractionally

zbMATH Keywords

graph algorithmsdirected graphslinkageErdőds-Pósa property

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Directed tree-width
• Introducing directed tree width
• Graph minors. V. Excluding a planar graph
• Quickly excluding a planar graph
• On Independent Circuits Contained in a Graph
• Large-treewidth graph decompositions and applications
• Polynomial treewidth forces a large grid-like-minor
• Graph minors. III. Planar tree-width
• Packing directed circuits
• Linearity of grid minors in treewidth with applications through bidimensionality
• Multicommodity flow, well-linked terminals, and routing problems
• Packing directed circuits fractionally
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• An excluded grid theorem for digraphs with forbidden minors
• The directed grid theorem
• Polynomial bounds for the grid-minor theorem
• The all-or-nothing flow problem in directed graphs with symmetric demand pairs
• A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
• Constant congestion routing of symmetric demands in planar directed graphs
• Polynomial planar directed grid theorem

Cited In (5)

• Packing Directed Cycles Quarter- and Half-Integrally
• Packing circuits into \(K_N\).
• Packing Odd Circuits
• Optimal packing of even circuits into a \(\text{DK}_ v\)
• Packing directed circuits exactly

This page was built for publication: Packing directed circuits quarter-integrally

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075819)