#TSP#

• Lucas Oliveira David, Universidade Federal de São Carlos - São Carlos, SP, Brasil.

Introduction

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. (Wikipedia)

Volunteer scientific initiation student in Graph Theory field, resulting in the paper "Twice-around a Shortest-path Tree Significantly Increases the Solution Cost".

The paper reports the empirical performance comparison between the classical Twice-around algorithm and a modified Twice-around which uses Dijkstra's shortest-path as sub-algorithm. Invariably, the classic Twice-around performed much better than the one with Dijkstra's.

References

• P. Feofiloff, "Algoritmos para Grafos" (in Portuguese), IME-USP, available: http://www.ime.usp.br/~pf/algoritmos_para_grafos
• M. E. J. Newman and M. Girvan, "Finding and evaluating community structure in networks", available: https://docs.google.com/file/d/0Bxl_AQ6nM3yXMENIUDk3aHhDazA