Packing in generalized kernel systems: a framework that generalizes packing of branchings

Autor:	Mario Leston-Rey, Yoshiko Wakabayashi
Rok vydání:	2014
Předmět:	Condensed Matter::Soft Condensed Matter Combinatorics Arborescence General Mathematics Numerical analysis Kernel system Digraph Computer Science::Computational Geometry COMBINATÓRIA Software Mathematics
Zdroj:	Repositório Institucional da USP (Biblioteca Digital da Produção Intelectual) Universidade de São Paulo (USP) instacron:USP
ISSN:	1436-4646 0025-5610
DOI:	10.1007/s10107-014-0746-4
Popis:	We study a framework, which we call a generalized kernel system, introduced by Frank. We prove some integral and fractional packing theorems in this framework which, in particular, imply an improvement over the best known upper bounds on the size of the packing, one due to Gabow and Manu, for packing arborescences from a given root, and another, due to Schrijver, for packing branchings from given root-sets in a digraph.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::68275e61c6263d92e4e2f10616eaee76 https://doi.org/10.1007/s10107-014-0746-4 Zobrazit plný text záznamu Full text from SpringerLink