Integral packing of branchings in capacitaded digraphs

Autor:	Mario Leston-Rey
Rok vydání:	2014
Předmět:	Discrete mathematics Mathematics::Combinatorics 021103 operations research Control and Optimization Applied Mathematics 0211 other engineering and technologies Digraph 010103 numerical & computational mathematics 02 engineering and technology 01 natural sciences Computer Science Applications Combinatorics Branching (linguistics) Computational Theory and Mathematics Computer Science::Discrete Mathematics Theory of computation Discrete Mathematics and Combinatorics 0101 mathematics Computer Science::Data Structures and Algorithms Mathematics
Zdroj:	Journal of Combinatorial Optimization. 31:506-514
ISSN:	1573-2886 1382-6905
DOI:	10.1007/s10878-014-9768-3
Popis:	We prove that an algorithm of Schrijver, that computes an integral packing of branchings in a capacitaded digraph, produces a packing with no more than $$m + r - 1$$m+r-1 different branchings, where $$m$$m is the number of arcs, and $$r$$r the number of root-sets of the digraph.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::931cf34e350881c279e1333ac33a5577 https://doi.org/10.1007/s10878-014-9768-3 Zobrazit plný text záznamu Full text from SpringerLink