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

DOI10.1007/3-540-59408-6_67MaRDI QIDQ5101431zbMATH OpenOpenAlexFDO

Authors Harold N. Gabow, K. S. Manu

Publication date 30 August 2022

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59408-6_67

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Packing Spanning Trees
• Integral packing of branchings in capacitaded digraphs
• Integral packing of trees and branchings
• Reachability in arborescence packings

Cites work

• A faster algorithm for finding edge-disjoint branchings
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• A good algorithm for edge-disjoint branching
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• Arc‐disjoint arborescences of digraphs
• Edge-disjoint branching in directed multigraphs
• Forests, frames, and games: Algorithms for matroid sums and applications
• Fractional covers for forests and matchings
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 3926633 (Why is no real title available?)
• scientific article; zbMATH DE number 3661345 (Why is no real title available?)
• scientific article; zbMATH DE number 1256704 (Why is no real title available?)
• scientific article; zbMATH DE number 3799695 (Why is no real title available?)
• scientific article; zbMATH DE number 910863 (Why is no real title available?)
• Minimum partition of a matroid into independent subsets
• NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS
• On N–Edge–Connected Digraphs
• On two minimax theorems in graph
• Strength and reinforcement of a network and tree packing
• Strength of a graph and packing of trees and branchings

Cited in

(20)

• The complexity of finding arborescences in hypergraphs
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Arborescence optimization problems solvable by Edmonds' algorithm
• On packing spanning arborescences with matroid constraint
• Packing arborescences in random digraphs
• An LP-based heuristic algorithm for the node capacitated in-tree packing problem
• Integral packing of trees and branchings
• On packing time-respecting arborescences
• Polymatroid-based capacitated packing of branchings
• The complexity of the node capacitated in-tree packing problem
• Packing arborescences
• Lagrangian-based column generation for the node capacitated in-tree packing problem
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• Packing arborescences in random digraphs
• Packing Spanning Trees
• scientific article; zbMATH DE number 871952 (Why is no real title available?)
• scientific article; zbMATH DE number 910863 (Why is no real title available?)
• A faster algorithm for packing branchings in digraphs
• Integral packing of branchings in capacitaded digraphs
• Restricted covering of digraphs with arborescences

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 Q5101431)