Algorithme le plus rapide connu pour trouver des chemins simples à travers un ensemble donné de sommets

Pour un graphe non orienté et un ensemble de sommets, ce qui est l'algorithme connu asymptotiquement le plus rapide pour trouver un chemin simple contenant tous les éléments de . Et si nous voulons que le chemin soit le plus court possible? $G$ $S$ $S$

ds.algorithms graph-algorithms time-complexity shuaoT
la source

Réponses:

Voir http://thorehusfeldt.files.wordpress.com/2010/08/soda2012_submission_247.pdf .

Andreas Björklund
la source

Hé, c'est un papier très cool! Merci pour le lien.

zotachidil

des points supplémentaires pour la décoration soignée sur la première page. Comment as-tu fais ça ?

Suresh Venkat

est-il évident qu'un algorithme pour trouver un cycle fonctionne pour un chemin?

didest

@Diego: Ajoutez une arête spécifiée entre les deux sommets que vous souhaitez être les extrémités du chemin.

Andreas Björklund