A nearly linear time algorithm for the half integral parity disjoint paths packing problem

MaRDI QIDQ4633933zbMATH OpenFDO

Authors Ken-ichi Kawarabayashi, Bruce Reed

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496898

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• An improved algorithm for the half-disjoint paths problem
• Improved algorithm for the half-disjoint paths problem
• Odd cycle packing
• Publication:3211338
• On the complexity of the disjoint paths problem

Cited in

(12)

• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements
• Half-integral linkages in highly connected directed graphs
• Shortest \((A+B)\)-path packing via hafnian
• Linear time parameterized algorithms for subset feedback vertex set
• Improved algorithm for the half-disjoint paths problem
• Subexponential algorithms for partial cover problems
• Combing a Linkage in an Annulus
• Odd cycle packing
• Approximating disjoint-path problems using packing integer programs
• An improved algorithm for the half-disjoint paths problem
• Faster algorithms for half-integral \(T\)-path packing

This page was built for publication: A nearly linear time algorithm for the half integral parity disjoint paths packing problem

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