A fast algorithm for the path 2-packing problem

DOI10.1007/S00224-008-9141-YzbMATH Open1183.68716OpenAlexW2077595059MaRDI QIDQ2268342FDOQ2268342

Authors Maxim Babenko

Publication date 5 March 2010

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-008-9141-y

zbMATH Keywords

polynomial-time algorithmpath packing\(T\)-paths

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• A Fast Algorithm for Path 2-Packing Problem
• Faster algorithms for half-integral \(T\)-path packing
• An improved algorithm for packing \(T\)-paths in inner Eulerian networks
• The path set packing problem
• STACS 2004

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 4103110 (Why is no real title available?)
• scientific article; zbMATH DE number 1775390 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 5691235 (Why is no real title available?)
• A Fast Algorithm for Path 2-Packing Problem
• A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
• A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons
• A short proof of Mader's \(\mathcal S\)-paths theorem
• An algorithm for packing non-zero \(A\)-paths in group-labelled graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Free multiflows in bidirected and skew-symmetric graphs
• Matroid matching and some applications
• On some connectivity properties of Eulerian graphs
• Packing non-returning A-paths
• Packing non-returning \(A\)-paths algorithmically
• Über die Maximalzahl kantendisjunkter A-Wege

Cited in

(9)

• Discrete convex functions on graphs and their algorithmic applications
• Algorithm to find a maximum 2-packing set in a cactus
• A Fast Algorithm for Path 2-Packing Problem
• Algebraic algorithms for linear matroid parity problems
• Finding Maximum Edge-Disjoint Paths Between Multiple Terminals
• An improved algorithm for packing \(T\)-paths in inner Eulerian networks
• Faster algorithms for half-integral \(T\)-path packing
• A fast implementation for the 2D/3D box placement problem
• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}

Describes a project that uses

Uses Software

• Algorithm 360

This page was built for publication: A fast algorithm for the path 2-packing problem

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