Sobre o problema de caminhos tropicais em grafos: formulação, heurística e resultados experimentais (2023)
- Authors:
- Autor USP: SAMPAIO, IGOR DE MORAES - EACH
- Unidade: EACH
- DOI: 10.11606/D.100.2023.tde-19062023-083841
- Subjects: TEORIA DOS GRAFOS; HEURÍSTICA
- Keywords: Caminho tropical; Coloração de grafos; Graph coloring; Integer linear programming; Programação linear inteira; Tropical path
- Agências de fomento:
- Language: Português
- Abstract: Neste trabalho, estudamos o problema do caminho tropical máximo em grafos, MTPP. Um caminho em um grafo colorido nos vértices é dito ser tropical se os vértices do caminho possuem as cores usadas pela coloração dos vértices grafo. Para o problema MTPP é dado um grafo e uma coloração de seus vértices, e o objetivo é encontrar um caminho cuja coloração use o maior número possível de cores desta coloração. A motivação para estudar o MTPP surge da constatação de que, até o início desta pesquisa, não havia na literatura abordagens baseadas em modelos de programação linear inteira, nem algoritmos heurísticos para o problema de interesse. Sabe-se que o MTPP é NP-difícil para grafos em geral, grafos direcionados acíclicos, grafos cacto e grafos de intervalo. Nesta pesquisa, foi desenvolvida uma modelagem para o problema MTPP como um problema de programação linear inteira para grafos simples e uma simplificação do modelo proposto para DAGs também é apresentada. Uma formulação similar é apresentada para uma segunda versão de otimização do problema em que o objetivo é encontrar um caminho tropical cuja soma dos pesos das arestas seja o menor possível. A contribuição principal desta pesquisa consiste na construção de uma heurística de tempo polinomial para o MTPP que juntamente com o modelo de PLI foi possível avaliar o desempenho de ambos por meio de experimentos computacionais em instâncias aleatórias e reais
- Imprenta:
- Data da defesa: 19.04.2023
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
ABNT
SAMPAIO, Igor de Moraes. Sobre o problema de caminhos tropicais em grafos: formulação, heurística e resultados experimentais. 2023. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2023. Disponível em: https://www.teses.usp.br/teses/disponiveis/100/100131/tde-19062023-083841/. Acesso em: 10 fev. 2026. -
APA
Sampaio, I. de M. (2023). Sobre o problema de caminhos tropicais em grafos: formulação, heurística e resultados experimentais (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/100/100131/tde-19062023-083841/ -
NLM
Sampaio I de M. Sobre o problema de caminhos tropicais em grafos: formulação, heurística e resultados experimentais [Internet]. 2023 ;[citado 2026 fev. 10 ] Available from: https://www.teses.usp.br/teses/disponiveis/100/100131/tde-19062023-083841/ -
Vancouver
Sampaio I de M. Sobre o problema de caminhos tropicais em grafos: formulação, heurística e resultados experimentais [Internet]. 2023 ;[citado 2026 fev. 10 ] Available from: https://www.teses.usp.br/teses/disponiveis/100/100131/tde-19062023-083841/
Informações sobre o DOI: 10.11606/D.100.2023.tde-19062023-083841 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
