Recoloração convexa de caminhos (2011)
- Autores:
- Autor USP: LIMA, KARLA ROBERTA PEREIRA SAMPAIO - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: OTIMIZAÇÃO COMBINATÓRIA
- Agências de fomento:
- Idioma: Português
- Resumo: O foco central desta tese é o desenvolvimento de algoritmos para o problema de recoloração convexa de caminhos. Neste problema, é dado um caminho cujos vértices estão coloridos arbitrariamente, e o objetivo é recolorir o menor número possível de vértices demodo a obter uma coloração convexa. Dizemos que uma coloração de um grafo é convexa se, para cada cor, o sbgrafo induzido pelos vértices dessa cor é convexo. Sabe-se que esse problema é NP-difícil. Associamos a este problema um poliedro, e estudamos sua estrutura facial, com vistas ao desenvolvimento de um algoritmo. Mostramos várias inequações válidas para esse poliedro,eprovamos que várias delas definem facetas. Apresentamos um algoritmo de programação dinâmica que resolve em tempo polinomial o problema da separação para uma classe grande deinequações que definem facetas. Implementamos um algoritmo branch-and-cut baseado nesses resultados, e realizamos testes computacionais com instâncias gradas aleatoriamente. Apresentamos adicionalmente uma heirística baseada numa formulação linear que obtivemos.
- Imprenta:
- Data da defesa: 16.11.2011
-
ABNT
LIMA, Karla Roberta Pereira Sampaio. Recoloração convexa de caminhos. 2011. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2011. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23012012-144246/. Acesso em: 23 abr. 2024. -
APA
Lima, K. R. P. S. (2011). Recoloração convexa de caminhos (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23012012-144246/ -
NLM
Lima KRPS. Recoloração convexa de caminhos [Internet]. 2011 ;[citado 2024 abr. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23012012-144246/ -
Vancouver
Lima KRPS. Recoloração convexa de caminhos [Internet]. 2011 ;[citado 2024 abr. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23012012-144246/
Como citar
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
