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 (breno-honorato@hotmail.com)2


1Universidade Federal do Ceará
2Universidade Estadual do Ceará

This paper appears in: Revista IEEE América Latina

Publication Date: Feb. 2016
Volume: 14,   Issue: 2 
ISSN: 1548-0992


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 n-1 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 Full-Text (422)]