Texto completo
| |
| Autor(es): |
Mário Leston Rey
Número total de Autores: 1
|
| Tipo de documento: | Tese de Doutorado |
| Imprenta: | São Paulo. |
| Instituição: | Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) |
| Data de defesa: | 2012-11-22 |
| Membros da banca: |
Yoshiko Wakabayashi;
Marcelo Henriques de Carvalho;
Orlando Lee;
Sostenes Luis Soares Lins;
Jose Coelho de Pina Junior
|
| Orientador: | Yoshiko Wakabayashi |
| Resumo | |
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. (AU) | |
| Processo FAPESP: | 00/09570-4 - Aspectos estruturais e algorítmicos de problemas em Teoria dos Grafos |
| Beneficiário: | Mario Leston Rey |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |