Some new results on node-capacitated packing of A-paths

DOI10.1145/1250790.1250878zbMath1231.05216OpenAlexW2005184452MaRDI QIDQ3549661

Gyula Pap

Publication date: 5 January 2009

Published in: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1250790.1250878

zbMATH Keywords

polynomial time algorithmmaximum packingGerard's proximity lemmanode-capacitated A-path packing algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Min-cost multiflows in node-capacitated undirected networks ⋮ Finding Maximum Edge-Disjoint Paths Between Multiple Terminals ⋮ Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees ⋮ A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Algebraic Algorithms for Linear Matroid Parity Problems ⋮ A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem ⋮ Faster algorithms for half-integral T -Path packing

This page was built for publication: Some new results on node-capacitated packing of A-paths