Hamiltonian cycle and TSP: A backtracking approach
Journal Title: International Journal on Computer Science and Engineering - Year 2011, Vol 3, Issue 4
Abstract
Backtracking is one of the strategies to reduce the complexity of a problem. Backtracking mainly useful when there is a no solution by going forward in that direction so we required backtracking from it to reduce the complexity and save the time. Backtracking has ability to give same result in far fewer attempts than the exhaustive or brute force method trials. This paper gives the recursive algorithm for Hamiltonian cycle and TSP (travelling salesman problem) based on the backtracking approach. If at any stage it is detected that the particular input or combination will not lead to an optimal solution than we can discard and a new input can be selected.
Authors and Affiliations
Dipak Patel , Nishant Doshi , Shakti Patel , Dishant Soni
Keywords
Related Articles
- EP ID EP119093
- DOI -
- Views 83
- Downloads 0
A Novel Session Based Dual Image Encoding and Hiding Technique Using DWT and Spread Spectrum
This work proposes a DWT based Steganographic technique. Cover image is decomposed into four sub bands using DWT. Two Encoded secret images are embedded within the HL and HH sub bands respectively. During embedding secre...
Search Engine Optimization through Spanning Forest Generation Algorithm
Search engine technology has had to scale dramatically to keep up with the growth of the web. With the tremendous growth of information available to end users through the Web, search engines come to play ever a more crit...
A Novel Benchmark K-Means Clustering on Continuous Data
Cluster analysis is one of the prominent techniques in the field of data mining and k-means is one of the most well known popular and partitioned based clustering algorithms. K-means clustering algorithm is widely used i...
Cryptosystem for Information Security
This paper introduces a symmetric cryptosystem for information. Algorithms are described for implementing the proposed method. Cryptanalysis of the proposed scheme is reported along with similar analysis for two popular...
Performance Evaluation and Optimization of TCP Parameters over Frame Relay Network
The TCP window size value, which is contained in the window size field of the TCP segment is a very important TCP Parameter. The window size value determines the number of bytes of data that can be sent before an acknowl...