Odwołanie do szybkiego algorytmu dla najkrótszych ścieżek wąskich gardeł

12

Szukam dobrego odniesienia do najkrótszych ścieżek wąskich gardeł. W szczególności, biorąc pod uwagę wierzchołki si na grafie bezkierunkowym z wagami krawędzi, potrzebujesz najkrótszej ścieżki od s do t, gdzie długość ścieżki jest maksymalną krawędzią na tej ścieżce. Można to rozwiązać w czasie O (n + m), znajdując środkową masę krawędzi i (ostrożnie) rekurencyjnie usuwając połowę krawędzi.

Czy ktoś zna odniesienia do tego?

ds.algorithms reference-request graph-algorithms Ben
źródło
Być może jest to kwestia sporna, ale problem, który opisujesz, to problem ścieżki minimax. Najkrótszą ścieżką z wąskim gardłem jest maksymalna wersja tego, co opisujesz. Algorytm dla jednej wersji generalnie (zawsze?) Daje algorytm dla drugiej wersji.
bbejot

Odpowiedzi:

10

PM Camerini (1978), Problem dotyczący drzewa opinającego min. I maks. Oraz niektóre rozszerzenia, Listy przetwarzania informacji 7 (1): 10–14, doi: 10.1016 / 0020-0190 (78) 90030-3

David Eppstein
źródło
5
Btw, jeśli chcesz rozwiązać wersję problemu z pojedynczym źródłem (iw pewnym sensie parami) dla grafów bezkierunkowych, możesz to zrobić w losowym czasie O (m + n): TC Hu zauważył w 1961 r., Że ścieżki wąskiego gardła dla wszystkich par są zakodowane w drzewie o maksymalnej długości; następnie algorytm drzewa rozpinającego czasowo minimalny Karger, Klein i Tarjan daje ci to, czego chcesz.
virgi
O ile mogę stwierdzić, referencja nie jest tym, czego potrzebuję. Ścieżka st w drzewie min-max nie jest koniecznie wąską wąską ścieżką st. Ponadto algorytm liniowego oczekiwanego czasu KKT nie jest tym, czego potrzebuję, ponieważ chcę deterministycznego, a nie oczekiwanego czasu działania. Mimo to dziękuję za pomoc.
Ben
4
W rzeczywistości ścieżka P w minimalnym drzewie rozpinającym T ma minimalny maksymalny ciężar krawędziowy na wszystkich ścieżkach. Załóżmy, że nie. Niech więc maksymalna krawędź P będzie e. Usunięcie e z T tworzy wycięcie wykresu. Rzeczywista ścieżka min 'max P musi mieć krawędź e' przechodzącą przez to cięcie. Dodanie e 'do T \ {e} tworzy nowe drzewo opinające T', które musi mieć mniejszy koszt niż T, ponieważ waga e 'jest co najwyżej maksymalną wagą krawędzi na P', która jest mniejsza niż w (e). Jest to sprzeczne z faktem, że T jest drzewem o rozpiętości min.
virgi