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

DOI10.1136/JECH.2006.053231zbMATH Open0920.90122OpenAlexW2114089855WikidataQ36943280 ScholiaQ36943280MaRDI QIDQ1290635FDOQ1290635

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

Recommendations

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

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)

Cited In (21)

• A generalized approximation framework for fractional network flow and packing problems
• Network strength games: the core and the nucleolus
• Restricted covering of digraphs with arborescences
• A linear programming approach to increasing the weight of all minimum spanning trees
• Polymatroid-based capacitated packing of branchings
• LP Relaxation and Tree Packing for Minimum $k$-Cut
• Algorithms for finding a rooted \((k,1)\)-edge-connected orientation
• An LP-based heuristic algorithm for the node capacitated in-tree packing problem
• Title not available (Why is that?)
• Integral packing of trees and branchings
• 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
• Fractional packing in ideal clutters
• A faster algorithm for packing branchings in digraphs
• Computing Weighted Strength and Applications to Partitioning
• Integral packing of branchings in capacitaded digraphs
• The complexity of the node capacitated in-tree packing problem
• On packing spanning arborescences with matroid constraint
• Faster algorithms for security games on matroids
• Packing in generalized kernel systems: a framework that generalizes packing of branchings
• Packing Spanning Trees

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)