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
-
ABNT
MOURA, Phablo Fernando Soares. Recoloração convexa de grafos algoritmos e poliedros. 2013. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2013. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-19112013-193725. Acesso em: 23 abr. 2024. -
APA
Moura, P. F. S. (2013). Recoloração convexa de grafos algoritmos e poliedros (Dissertação (Mestrado). 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. Recoloração convexa de grafos algoritmos e poliedros [Internet]. 2013 ;[citado 2024 abr. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-19112013-193725 -
Vancouver
Moura PFS. Recoloração convexa de grafos algoritmos e poliedros [Internet]. 2013 ;[citado 2024 abr. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-19112013-193725
Como citar
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
