Finding the hamiltonian path in a directed cyclic graph
i want to know if there is an algorithm to find the longest cyclic path in a directed weighted graph (i think this i a problem of finding the largest Hamiltonian sub-graph).
I need 开发者_C百科to start from one vertex and return to the same vertex, whit the most possible nodes traversed.
Thanks
This problem is a special case of the optimal euler circuit problem where all edge weights are 1; the original problem is NP-complete. Moreover, this problem can be used to solve the Hamiltonian Graph problem (a Hamiltonian cycle exists if and only if the optimal circuit traverses all nodes), so it remains NP-complete even with the special case restriction. Any exact solution will (unless P = NP) require exponential time. You may find this paper helpful; it describes a polynomial-time approximation algorithm for this problem, as well as a polynomial-time algorithm for cases where the graph has at most degree 4:
Qiao, Yu. "Optimal Euler Circuit of Maximum Contiguous Cost." IEICE Trans. Fundamentals E90-A, no. 1 (2007): 274-280.
A good approximation gives the Hilbert Curve.
精彩评论