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

DOI10.1136/JECH.2006.053231MaRDI QIDQ1290635zbMATH OpenOpenAlexWikidataFDO

Authors Harold N. Gabow, K. S. Manu

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)

Recommendations

• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Packing Spanning Trees
• Integral packing of trees and branchings

Cited in

(28)

• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• A faster algorithm for packing branchings in digraphs
• Restricted covering of digraphs with arborescences
• The complexity of the node capacitated in-tree packing problem
• A linear programming approach to increasing the weight of all minimum spanning trees
• Algorithms for finding a rooted \((k,1)\)-edge-connected orientation
• Lagrangian-based column generation for the node capacitated in-tree packing problem
• Integral packing of branchings in capacitaded digraphs
• Computing weighted strength and applications to partitioning
• Packing arborescences
• Packing in generalized kernel systems: a framework that generalizes packing of branchings
• Network strength games: the core and the nucleolus
• A generalized approximation framework for fractional network flow and packing problems
• Faster algorithms for security games on matroids
• Polymatroid-based capacitated packing of branchings
• On packing time-respecting arborescences
• LP relaxation and tree packing for minimum \(k\)-cut
• Fractional packing in ideal clutters
• An LP-based heuristic algorithm for the node capacitated in-tree packing problem
• Integral packing of trees and branchings
• Packing arborescences in random digraphs
• Packing Spanning Trees
• 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
• On packing spanning arborescences with matroid constraint
• Old and new results on packing arborescences in directed hypergraphs
• scientific article; zbMATH DE number 910863 (Why is no real title available?)
• Packing arborescences in random digraphs

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

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