RT conferenceObject
T1 Goodness of cycles and Hamiltonian paths
A1 de Arriba Perez, Francisco
A1 Corbacho, Cristina
A1 Somoza López, María del Carmen
A1 Vidal Vázquez, Ricardo
A2 Universidade de Vigo
K1 12 Matemáticas
AB Introduction. The problem of finding an optimal Hamiltonian cycle on a set of complex plane points (TSP) is a well-known open problem. If the number of points is small, we can simply calculate all the possible cycles and stay with a shorter one, but this strategy is not viable when the number of points is large. Historically the problem has been addressed by building partitions of the plane containing a small number of vertices, in these subsets it is easy to determine optimal cycles and finally design appropriate strategies to paste the previous paths thus obtaining an approximation of the solution to the problem posed (see [4])We have designed (see [1]) an algorithm that, in a reasonable time and in a personal computer, gives us a solution to the problem posed although the number of points is large. In this algorithm we propose a different strategy, we consider a partition of the set of points V in its different levels of convexity {V1, V2, ··· , Vp},thinking that the geometry of the distribution of the points would facilitate the connection between the different elements of the partition. [...]
SN 9788481588170
YR 2019
FD 2019
LK http://hdl.handle.net/11093/7059
UL http://hdl.handle.net/11093/7059
LA eng
NO En 2019 Interdisciplinary Colloquium in Topology and its Applications (147-154)
DS Investigo
RD 18-sep-2024