Um arcabouço generalizado para empacotamento de ramificações e outras estruturas combinatórias

• Ano de defesa: 2012
• Autor(a) principal: Rey, Mário Leston
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: arborescences; arborescências; branchings; laminaridade; laminarity; ramificações; submodularidade; submodularity; supermodularidade; supermodularity.
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-15022013-111836/

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.