A faster algorithm for packing branchings in digraphs

DOI10.1016/J.DAM.2015.05.016MaRDI QIDQ494431zbMATH OpenOpenAlexFDO

Authors Orlando Lee, Mario Leston-Rey

Publication date 1 September 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.3480

zbMATH Keywords

combinatorial optimizationpacking of branchings

Mathematics Subject Classification ID

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

Abstract: We consider the problem of finding an integral packing of branchings in a capacitated digraph with root-set demands. Schrijver described an algorithm that returns a packing with at most m+n^3+r branchings that makes at most m(m+n^3+r) calls to an oracle that basically computes a minimum cut, where n is the number of vertices, m is the number of arcs and r is the number of root-sets of the input digraph. In this work we provide an algorithm, inspired on ideas of Schrijver and on an paper of Gabow and Manu, that returns a packing with at most m+r-1 branchings and makes at most 2n+m+r-1 oracle calls.

Recommendations

• Integral packing of branchings in capacitaded digraphs
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Integral packing of trees and branchings
• scientific article; zbMATH DE number 7378329

Cites work

• scientific article; zbMATH DE number 5764894 (Why is no real title available?)
• scientific article; zbMATH DE number 634030 (Why is no real title available?)
• A note on disjoint arborescences
• An integer analogue of Carathéodory's theorem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Connections in combinatorial optimization
• Edge-Disjoint Spanning Trees of Finite Graphs
• Improved bound for the Carathéodory rank of the bases of a matroid
• Minimum partition of a matroid into independent subsets
• On two minimax theorems in graph
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Packing arborescences
• Packing in generalized kernel systems: a framework that generalizes packing of branchings
• Polyhedra with the integer Carathéodory property

Cited in

(7)

• Integral packing of branchings in capacitaded digraphs
• Packing in generalized kernel systems: a framework that generalizes packing of branchings
• Integral packing of trees and branchings
• Stronger bounds and faster algorithms for packing in generalized kernel systems
• The \(b\)-branching problem in digraphs
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}

This page was built for publication: A faster algorithm for packing branchings in digraphs

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