A faster algorithm for packing branchings in digraphs

DOI10.1016/J.DAM.2015.05.016zbMATH Open1319.05060arXiv1306.3480OpenAlexW1540276928MaRDI QIDQ494431FDOQ494431

Authors: Orlando Lee, Mario Leston-Rey 

Publication date: 1 September 2015

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

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.

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

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

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)

Cites Work

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

Cited In (7)

• The \(b\)-branching problem in digraphs
• Integral packing of trees and branchings
• Stronger bounds and faster algorithms for packing in generalized kernel systems
• Integral packing of branchings in capacitaded digraphs
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Packing in generalized kernel systems: a framework that generalizes packing of branchings
• 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)