Faster algorithms for half-integral T-path packing

DOI10.4230/LIPICS.ISAAC.2017.8MaRDI QIDQ5136223zbMATH OpenOpenAlexFDO

Authors Stepan Artamonov, Maxim Babenko

Publication date 25 November 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.ISAAC.2017.8

zbMATH Keywords

graph algorithmsmatchingsmultiflowspath packings

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) 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
• A nearly linear time algorithm for the half integral parity disjoint paths packing problem
• A fast algorithm for the path 2-packing problem
• A Fast Algorithm for Path 2-Packing Problem

Cites work

• Clique partitions, graph compression and speeding-up algorithms
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Matching theory
• Maximum skew-symmetric flows and matchings
• Min-cost multiflows in node-capacitated undirected networks
• Some new results on node-capacitated packing of A-paths
• Triangle-free 2-matchings revisited
• Über die Maximalzahl kantendisjunkter A-Wege

Cited in

(5)

• A fast algorithm for the path 2-packing problem
• A Fast Algorithm for Path 2-Packing Problem
• An improved algorithm for packing \(T\)-paths in inner Eulerian networks
• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
• The Lovász-Cherkassky theorem in countable graphs

This page was built for publication: Faster algorithms for half-integral \(T\)-path packing

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