• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tese de Doutorado
DOI
10.11606/T.45.2012.tde-15022013-111836
Documento
Autor
Nome completo
Mário Leston Rey
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2012
Orientador
Banca examinadora
Wakabayashi, Yoshiko (Presidente)
Carvalho, Marcelo Henriques de
Lee, Orlando
Lins, Sostenes Luis Soares
Pina Junior, Jose Coelho de
Título em português
Um arcabouço generalizado para empacotamento de ramificações e outras estruturas combinatórias
Palavras-chave em português
arborescências
laminaridade
ramificações
submodularidade
supermodularidade
Resumo em português
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.
Título em inglês
A general framework for packing branchings and other combinatorial structures
Palavras-chave em inglês
arborescences
branchings
laminarity
submodularity
supermodularity.
Resumo em inglês
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.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
leston.pdf (616.43 Kbytes)
Data de Publicação
2013-02-15
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2019. Todos os direitos reservados.