Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Longest path approximation algorithm from a given node

I'm looking for an approximation algorithm for the following problem - I have an unweighted, undirected graph, with cycles, and want to find the longest path starting from a given node. I do value speed over performance (so a O(n^5) algorithm would probably be an overkill).

This is not homework (I swear!) or work related, but I will appreciate any tip you might have.

like image 570
r0u1i Avatar asked Feb 08 '10 10:02

r0u1i


1 Answers

I'm looking for an approximation algorithm for the following problem ...

Scientists are looking for it as well. They have also proved that polynomial constant-factor approximation doesn't exist if P ≠ NP. And the abstract of this article claims that it contains an approximation algorithm for your problem.

like image 136
P Shved Avatar answered Nov 18 '22 06:11

P Shved