2
Existe-t-il un algorithme de temps polynomial pour le problème de vendeur itinérant sur un graphe orienté complet?TSP pour un graphe orienté complet
A
Répondre
1
Improbable. S'il y en avait un, vous pourriez prendre n'importe quel graphique et ajouter tous les bords manquants avec un poids très élevé. Cela permettrait de résoudre la version standard du problème, qui est connue pour être NP-difficile.