%0 Journal Article
%T Restricted Backtracked Algorithm For Hamiltonian Circuit in Undirected Graph
%A Vinay Kumar
%J BVICAM's International Journal of Information Technology
%D 2010
%I Bharati Vidyapeeth's Institute of Computer Applications and Management
%X 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.
%K articulation point
%K complexity class
%K P
%K NP
%K Hamiltonian graph
%K connected graph
%K line sweeping
%K restricted backtracking
%U http://www.bvicam.ac.in/bijit/Downloads/pdf/issue4/04.pdf