Najszybszy znany algorytm znajdowania prostych ścieżek przez dany zestaw wierzchołków

Dla nieukierunkowane wykres i dany zbiór wierzchołków, co jest znane asymptotycznie najszybciej Algorytm znalezienia prostą drogę, zawierający wszystkie elementy . Co jeśli wymagamy, aby ścieżka była jak najkrótsza? $G$ $S$ $S$

ds.algorithms graph-algorithms time-complexity

— ShuaoT
źródło

Odpowiedzi:

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

— Andreas Björklund
źródło

Hej, to bardzo fajny papier! Dzięki za link.

— zotachidil

dodatkowe punkty za zgrabną dekorację na pierwszej stronie. Jak to zrobiłeś ?

— Suresh Venkat,

czy jest oczywiste, że algorytm znajdowania cyklu działa dla ścieżki?

— zrobił

@Diego: Dodaj określoną krawędź między dwoma wierzchołkami, które mają być punktami końcowymi ścieżki.

— Andreas Björklund,