Packing directed circuits quarter-integrally

DOI10.4230/LIPICS.ESA.2019.72MaRDI QIDQ5075819zbMATH OpenFDO

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

zbMATH Keywords

graph algorithmsdirected graphslinkageErdőds-Pósa property

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

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

Cites work

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

Cited in

(5)

• Packing circuits into \(K_N\).
• Optimal packing of even circuits into a \(\text{DK}_ v\)
• Packing Odd Circuits
• Packing Directed Cycles Quarter- and Half-Integrally
• 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)