Schnellster bekannter Algorithmus zum Finden einfacher Pfade durch einen bestimmten Satz von Eckpunkten

Was ist für einen ungerichteten Graphen und eine gegebene Menge von Eckpunkten der asymptotisch schnellste bekannte Algorithmus zum Finden eines einfachen Pfades, der alle Elemente von . Was ist, wenn der Weg so kurz wie möglich sein soll? $G$ $S$ $S$

ds.algorithms graph-algorithms time-complexity shuaoT
quelle

Antworten:

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

Andreas Björklund
quelle

Hey, das ist ein sehr cooles Papier! Danke für den Link.

Zotachidil

Extrapunkte für die ordentliche Dekoration auf der Titelseite. Wie hast du das gemacht ?

Suresh Venkat

Ist es offensichtlich, dass ein Algorithmus zum Finden eines Zyklus für einen Pfad funktioniert?

Didest

@Diego: Fügen Sie eine bestimmte Kante zwischen den beiden Scheitelpunkten hinzu, die Endpunkte des Pfads sein sollen.

Andreas Björklund