我正在寻找以下问题的近似算法 - 我有一个未加权的无向图,带有循环,并且想要找到从给定节点开始的最长路径。 我确实重视速度而不是性能(因此 O(n^5) 算法可能有点矫枉过正)。
这不是家庭作业(我发誓!)或与工作相关,但我将不胜感激您提供的任何提示。
最佳答案
I'm looking for an approximation algorithm for the following problem ...
科学家们也在寻找它。他们还有proved如果 P ≠ NP,则多项式常数因子近似不存在。和摘要this文章声称它包含针对您的问题的近似算法。
关于algorithm - 来自给定节点的最长路径近似算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2220779/