Ver registro no DEDALUS
Exportar registro bibliográfico

Recolocação convexa de caminhos (2011)

  • Authors:
  • USP affiliated authors: LIMA, KARLA ROBERTA PEREIRA SAMPAIO - IME
  • USP Schools: IME
  • Sigla do Departamento: MAC
  • Subjects: OTIMIZAÇÃO COMBINATÓRIA
  • 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 online ao documento

    Acesso à fonte or search this record in

    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. Recolocaçã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). Recolocaçã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. Recolocaçã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. Recolocaçã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 - 2019