Algorithme d'approximation du plus long chemin d'un nœud donné

Question

Je cherche un algorithme d'approximation pour le problème suivant - J'ai un graphe non pondéré, non orienté, avec des cycles, et je veux trouver le chemin le plus long à partir d'un nœud donné. J'estime la vitesse par rapport à la performance (donc un algorithme O (n^5) serait probablement excessif).

Ce ne sont pas des devoirs (je le jure!) Ou liés au travail, mais j'apprécierai n'importe quel conseil que vous pourriez avoir.

Answer 1

Je cherche un algorithme d'approximation pour le problème suivant ...

Les scientifiques cherchent aussi. Ils ont aussi proved que l'approximation du facteur constant polynomial n'existe pas si P ≠ NP. Et le résumé de l'article this prétend qu'il contient un algorithme d'approximation pour votre problème.