Faster algorithms for half-integral T-path packing

DOI10.4230/LIPICS.ISAAC.2017.8zbMATH Open1457.68200OpenAlexW2782967788MaRDI QIDQ5136223FDOQ5136223

Authors: Stepan Artamonov, Maxim Babenko 

Publication date: 25 November 2020

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

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

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)

Cites Work

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

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
• The Lovász-Cherkassky theorem in countable graphs
• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}

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)