Exportar registro bibliográfico

Recoloração convexa de caminhos (2011)

  • Authors:
  • Autor USP: LIMA, KARLA ROBERTA PEREIRA SAMPAIO - IME
  • Unidade: IME
  • Sigla do Departamento: MAC
  • Assunto: OTIMIZAÇÃO COMBINATÓRIA
  • Agências de fomento:
  • Language: Português
  • Abstract: 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
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      LIMA, Karla Roberta Pereira Sampaio; WAKABAYASHI, Yoshiko. Recoloração convexa de caminhos. 2011.Universidade de São Paulo, São Paulo, 2011. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23012012-144246/ >.
    • APA

      Lima, K. R. P. S., & Wakabayashi, Y. (2011). Recoloração convexa de caminhos. 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, Wakabayashi Y. Recoloração convexa de caminhos [Internet]. 2011 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23012012-144246/
    • Vancouver

      Lima KRPS, Wakabayashi Y. Recoloração convexa de caminhos [Internet]. 2011 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23012012-144246/


Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2020