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

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

Recommendations

• An improved algorithm for the half-disjoint paths problem
• Improved algorithm for the half-disjoint paths problem
• Odd cycle packing
• scientific article; zbMATH DE number 4191702
• On the complexity of the disjoint paths problem

Cited in

(12)

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

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)