Алгоритм аппроксимации наибольшего пути от заданного узла

Question

Я ищу алгоритм аппроксимации для следующей задачи - у меня есть невзвешенный ненаправленный граф с циклами, и я хочу найти самый длинный путь, начиная с данного узла. Я ценю скорость за производительность (поэтому алгоритм O (n ^ 5), вероятно, будет излишним).

Это не домашняя работа (клянусь!) Или связанная с работой работа, но я буду признателен за любой совет, который вы можете получить.

Answer 1

Я ищу алгоритм аппроксимации для следующей задачи ...

Ученые также ищут его.Они также доказали , что полиномиальное приближение с постоянным множителем не существует, если P ≠ NP.А в аннотации этой статьи утверждается, что она содержит алгоритм аппроксимации для вашей задачи.