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

• 成果类型: Article
• 署名作者: Leston-Rey, Mario; Wakabayashi, Yoshiko
• 署名单位: Universidade de Sao Paulo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0746-4
• 发表日期: 2015
• 页码: 209-251
• 关键词: graphs; arborescences

摘要

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.