A general framework for packing branchings and other combinatorial structures

Author(s)

Mário Leston Rey

• Document type: Doctoral Thesis
• Press: São Paulo.
• Institution: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
• Defense date: 2012-11-22

Examining board members

Yoshiko Wakabayashi; Marcelo Henriques de Carvalho; Orlando Lee; Sostenes Luis Soares Lins; Jose Coelho de Pina Junior

• Advisor: Yoshiko Wakabayashi

Abstract

We study a framework, which we call a generalized kernel system, introduced by Frank. We prove some integral and fractional packing theorems on this framework which, in particular, imply an improvement on the best upper bounds currently known, one due to Schrijver, for packing branchings from a given root-sets, and another, due to Gabow and Manu, for packing spanning arborescences from a given root. We also establish the polynomial time complexity, modulo a separation oracle, of a related minimization problem involving a polyhedron derived from this framework. (AU)