Packing algorithms for arborescences (and spanning trees) in capacitated graphs

DOI10.1136/JECH.2006.053231zbMath0920.90122OpenAlexW2114089855WikidataQ36943280 ScholiaQ36943280MaRDI QIDQ1290635

K. S. Manu, Harold N. Gabow

Publication date: 15 September 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1136/jech.2006.053231

zbMATH Keywords

coveringNewton's methodarborescence packingcapacitated digraphslaminar family of setspacking spanning trees

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (16)

The complexity of the node capacitated in-tree packing problem ⋮ Stronger bounds and faster algorithms for packing in generalized kernel systems ⋮ Fast approximation for computing the fractional arboricity and extraction of communities of a graph ⋮ Algorithms for finding a rooted \((k,1)\)-edge-connected orientation ⋮ Computing Weighted Strength and Applications to Partitioning ⋮ Fractional packing in ideal clutters ⋮ A linear programming approach to increasing the weight of all minimum spanning trees ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Faster algorithms for security games on matroids ⋮ A faster algorithm for packing branchings in digraphs ⋮ A generalized approximation framework for fractional network flow and packing problems ⋮ An LP-based heuristic algorithm for the node capacitated in-tree packing problem ⋮ Integral packing of branchings in capacitaded digraphs ⋮ Packing in generalized kernel systems: a framework that generalizes packing of branchings ⋮ Network strength games: the core and the nucleolus ⋮ Polymatroid-based capacitated packing of branchings

This page was built for publication: Packing algorithms for arborescences (and spanning trees) in capacitated graphs