Sobre o Problema do Caixeiro Viajante com Drone - Hokama, Pedro H. D. B.; Lintzmayer, Carla N.; San Felice, Mário César (Anais do Encontro de Teoria da Computação (ETC); 2024: Anais do IX Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2024.2324, 2024)
Abordamos o problema do Caixeiro Viajante com Companheiro Voador, mostramos uma propriedade estrutural respeitada por uma solução ótima para qualquer instância, e usamos a mesma para propor o algoritmo mais eficiente da literatura dentre os que criam soluções baseadas na inserção do drone em ciclos Hamiltonianos. Nosso algoritmo leva tempo linear para ciclos obtidos pela heurística Nearest Neighbor.