A nearly linear time algorithm for the half integral parity disjoint paths packing problem
zbMATH Open1423.68349MaRDI QIDQ4633933FDOQ4633933
Authors: Ken-ichi Kawarabayashi, Bruce Reed 
Publication date: 6 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=1496898
Recommendations
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)
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)
