Academic Journals Database
Disseminating quality controlled scientific knowledge

Restricted Backtracked Algorithm For Hamiltonian Circuit in Undirected Graph

Author(s): Vinay Kumar

Journal: BVICAM's International Journal of Information Technology
ISSN 0973-5658

Volume: 2;
Issue: 2;
Date: 2010;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

Keywords: articulation point | complexity class | P | NP | Hamiltonian graph | connected graph | line sweeping | restricted backtracking

While determining whether a graph is Hamiltonian, it is enough to show existence of a Hamiltonian cycle in it. An algorithm based on restricted backtracking is presented in the paper that uses tie breaking rules to reduce the possible number of backtrackings. If x is any intermediate node in HC then once its neighbour y has been visited from x, x is no longer required so drop it and process is continued on the remaining subgraph. Each node is visited exactly once in a HC except the start node. Adjacency matrix is used to encode the graph. Prevention of backtracking is achieved up to next node from start node. From third node onward, wherever it is not possible to break tie uniquely, a provision for backtracking is kept only for tied nodes. Time complexity of algorithm is O(n4)*B(n) in the worst case where B(n) is a factor due to possible backtracking. It returns O(n2) in the best case and O(n3)*B(n) on the average.
Save time & money - Smart Internet Solutions     

Tango Rapperswil
Tango Rapperswil