Um arcabouço generalizado para empacotamento de ramificações e outras estruturas combinatórias
| Autor: | Rey, Mário Leston |
|---|---|
| Jazyk: | portugalština |
| Rok vydání: | 2012 |
| Předmět: | |
| Druh dokumentu: | Tese de Doutorado |
| Popis: | Nesta tese, estudamos um arcabouço, introduzido por Frank, que denominamos de sistemas generalizados de núcleos. Provamos teoremas sobre empacotamentos de certos objetos combinatórios neste arcabouço, tanto para o caso inteiro quanto para o fracionário. Estes teoremas, em particular, implicam em uma melhora nos limitantes superiores de Schrijver, para o empacotamento de ramificações, e de Gabow e Manu, para o empacotamento de arborescências. Além disso, também provamos que o problema de minimização num poliedro relacionado pode ser resolvido em tempo polinomial, dado um oráculo de separação. 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. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|