Exportar registro bibliográfico

Recoloração convexa de grafos algoritmos e poliedros (2013)

  • Autores:
  • Autor USP: MOURA, PHABLO FERNANDO SOARES - IME
  • Unidade: IME
  • Sigla do Departamento: MAC
  • Assunto: COMBINATÓRIA
  • Agências de fomento:
  • Idioma: Português
  • Resumo: Neste trabalho, estudamos o problema da recoloração convexa de grafos, denotado por RC. Dizemos que uma coloração dos vértices de um grafo G é convexa se, para cada cor atribuída d, os vértices de G com a cor d induzem um subgrafo conexo. No problema RC, é dado um grafo G e uma coloração de seus vértices, e o objetivo é recolorir o menor número possível de vértices de G tal que a coloração resultante seja convexa. A motivação para o estudo deste problema surgiu em contexto de árvores filogenéticas. Sabe-se que este problema é NP-difícil mesmo quando G é um caminho. Mostramos que o problema RC parametrizado pelo número de mudanças de cor é W[2]-difícil mesmo se a coloração inicial usa apenas duas cores. Além disso, provamos alguns resultados sobre a inaproximabilidade deste problema. Apresentamos uma formulação inteira para a versão com pesos do problema RC em grafos arbitrários, e então a especializamos para o caso de árvores. Estudamos a estrutura facial do politopo definido como a envoltória convexa dos pontos inteiros que satisfazem as restrições da formulação proposta, apresentamos várias classes de desigualdades que definem facetas e descrevemos os correspondentes algoritmos de separação. Implementamos um algoritmo branch-and-cut para o problema RC em árvores e mostramos os resultados computacionais obtidos com uma grande quantidade de instâncias que representam árvores filogenéticas reais. Os experimentos mostram que essa abordagem pode ser usada para resolver instâncias da ordem de 1500 vértices em 40 minutos, um desempenho muito superior ao alcançado por outros algoritmos propostos na literatura.
  • Imprenta:
  • Data da defesa: 07.08.2013
  • Acesso à fonte
    Como citar
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      MOURA, Phablo Fernando Soares; WAKABAYASHI, Yoshiko. Recoloração convexa de grafos algoritmos e poliedros. 2013.Universidade de São Paulo, São Paulo, 2013. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-19112013-193725 >.
    • APA

      Moura, P. F. S., & Wakabayashi, Y. (2013). Recoloração convexa de grafos algoritmos e poliedros. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-19112013-193725
    • NLM

      Moura PFS, Wakabayashi Y. Recoloração convexa de grafos algoritmos e poliedros [Internet]. 2013 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-19112013-193725
    • Vancouver

      Moura PFS, Wakabayashi Y. Recoloração convexa de grafos algoritmos e poliedros [Internet]. 2013 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-19112013-193725

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

Biblioteca Digital de Produção Intelectual da Universidade de São Paulo     2012 - 2021