Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I have an un-directed un-weighted graph. It contains cycles. I would like to find the path which visits the most nodes with no repeat visits to any node. Since this is a graph traversal, you can start and end at any node you like.

Background Research: I have looked at Travelling Salesman Problem (TSP); this problem is different and does NOT allow you to finish where you started from and there are no weights. I have looked at several other algorithms, but have found none suitable for this problem.

Graph Size: There are 100 nodes in the graph; with 10 disconnected nodes.

share|improve this question
    
Maybe you are interested in Returning Paths on Cubic Graphs Without Backtracking... –  draks ... Nov 23 '12 at 20:49
add comment

1 Answer

This problem is still difficult, it is known as Hamiltonian path, and NP-complete. It doesn't really make a difference if the path is closed (a circuit) or not. Just ask the HAM-PATH problem for every pair of endpoints of all edges and you could solve HAM-CIRCUIT.

share|improve this answer
    
Thanks! What is HAM-PATH, HAM-CIRCUIT is it just your notation or some library in Matlab? –  Chirayu Shishodiya Nov 23 '12 at 20:15
    
Also there may not be any Hamiltonian path or cycle in my problem, I just want to visit the max number of nodes. –  Chirayu Shishodiya Nov 23 '12 at 20:20
    
No its just a short cut for the Hamiltonian Path problem, and the Hamiltonian Circuit problem. –  A.Schulz Nov 23 '12 at 20:20
    
Yeah, but the maximum could be the number of nodes and thus you can detect a Hamiltonian Path with your algorithm. Just ask if the maximum path visits all nodes. –  A.Schulz Nov 23 '12 at 20:23
    
I think I will write an algorithm of my own which will find the path which visits most nodes. Since there are 90 nodes, there are 90 * 89 combinations of start-end nodes which is roughly 8100 Hamiltonian Path problems; and I am not even sure that a Hamiltonian Path exists. So it could be an exercise in vain if I proceed with finding a Hamiltonian Path problem. –  Chirayu Shishodiya Nov 24 '12 at 8:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.