A Faster Algorithm for Packing Branchings in Digraphs
| Autor: | Orlando Lee, Mario Leston-Rey |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: |
Discrete mathematics
FOS: Computer and information sciences Arborescence Discrete Mathematics (cs.DM) Applied Mathematics Graph theory Digraph Oracle Combinatorics Packing problems Minimum cut FOS: Mathematics Discrete Mathematics and Combinatorics Combinatorial optimization Mathematics - Combinatorics Combinatorics (math.CO) Algorithm Mathematics MathematicsofComputing_DISCRETEMATHEMATICS Computer Science - Discrete Mathematics |
| Popis: | 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. We are fixing a flaw in the proof |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|