%0 Journal Article
%T A Faster Algorithm for Packing Branchings in Digraphs
%A Orlando Lee
%A Mario Leston Rey
%J Computer Science
%D 2013
%I arXiv
%X 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.
%U http://arxiv.org/abs/1306.3480v2