Um novo algoritmo para encontrar tours e circuitos hamiltonianos em grafos
(A New Algorithm for Finding all Tours and Hamiltonian Circuits in Graphs)
Jose Lassance Castro Silva (lassance@lia.ufc.br)^{1}, Leonardo Sampaio Rocha (leonardo.sampaio@uece.br)^{2}, Breno Castro Honorato Silva (brenohonorato@hotmail.com)^{2}
^{1}Universidade Federal do Ceará ^{2}Universidade Estadual do Ceará
This paper appears in: Revista IEEE América Latina
Publication Date: Feb. 2016
Volume: 14, Issue: 2
ISSN: 15480992
Abstract:
This paper presents a new algorithm that finds all tours and Hamiltonian circuits in graphs. The algorithm makes the search for tours through the construction of n (number of nodes do graph) trees, one for each node of the graph. In the tree, all possible paths are configured from the initial node to the other nodes without repetition. The n1 long paths are the tours of the graph. When a tour is in the tree and there is an edge in the graph connecting the end node to the start node of this tour, then a Hamiltonian circuit was found. The algorithm is easy to program and does not use recursion. The algorithm was applied to solve a problem of operational research within the graph theory. Several computational experiments were produced to measure the performance of the method in consolidated problem instances of literature.
Index Terms:
Graph Theory, Operational Research, Flowshop Scheduling Problem, Permutation.
Documents that cite this
document
This function is not implemented yet.
[PDF FullText (422)]
