4
$\begingroup$

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.

  • 0
    Maybe you are interested in [Returning Paths on Cubic Graphs Without Backtracking](http://math.stackexchange.com/q/177722/19341)...2012-11-23

2 Answers 2