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 117
- Downloads 0
SOFTWARE ARCHITECTURE BASED REGRESSION TESTING
Software architecture plays a significant role in development of a dependable system. The purpose of regression testing is to make the system fault tolerant. The amalgamation of these two, results in the development of a...
Comparative Study of Static Task Scheduling Algorithms for Heterogeneous Systems
On the distributed or parallel heterogeneous computing systems, an application is usually decomposed into several interdependent sets of co-operating subtasks and assigned to a set of available processors for execution....
VoIP over WMN: Effect of packet aggregation
VoIP services are getting more and more popular day by day. In order to meet the users demand for such services irrespective of users location requires wide area wireless coverage .To this extent, wireless mesh networks...
Prevention Of WormholeAttacks In Geographic Routing Protocol
As mobile ad hoc network applications are deployed, security emerges as a central requirement..Position aided routing protocols can offer a significant performance increase over traditional ad hoc routing protocols. Boun...
Spam Classification using new kernel function in Support Vector Machine
Due to the increase in internet users, there is a rapid growth in spam e-mails. In recent years, kernel function have received major attention, particularly due to the increased popularity of Support Vector Machine. It i...