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
- Status:
- Artigo possui versão em acesso aberto em repositório (Green Open Access)
- Versão do Documento:
- Versão submetida (Pré-print)
- Acessar versão aberta:
-
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://teses.usp.br/teses/disponiveis/100/100131/tde-19062023-083841/. Acesso em: 03 abr. 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://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 abr. 03 ] Available from: https://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 abr. 03 ] Available from: https://teses.usp.br/teses/disponiveis/100/100131/tde-19062023-083841/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
