Referenz für einen schnellen Algorithmus für Engpass-Kurzstrecken

12

Ich suche eine gute Referenz für Engpass kürzeste Wege. Insbesondere möchten Sie bei den Eckpunkten s und t in einem ungerichteten Diagramm mit Kantengewichten den kürzesten Pfad von s nach t, ​​wobei die Länge eines Pfads die maximale Kante auf diesem Pfad ist. Dies kann in O (n + m) gelöst werden, indem das mittlere Kantengewicht ermittelt und die Hälfte der Kanten (vorsichtig) rekursiv gelöscht wird.

Kennt jemand eine Referenz dafür?

ds.algorithms reference-request graph-algorithms Ben
quelle
Vielleicht ist dies ein Streitpunkt, aber das Problem, das Sie beschreiben, ist das Minimax-Pfadproblem. Der kürzeste Weg zum Engpass ist die Max-Min-Version Ihrer Beschreibung. Ein Algorithmus für eine der Versionen liefert im Allgemeinen (immer?) Einen Algorithmus für die andere Version.
Bejot

Antworten:

10

PM Camerini (1978), Das Min-Max-Spanning-Tree-Problem und einige Erweiterungen, Information Processing Letters 7 (1): 10-14, doi: 10.1016 / 0020-0190 (78) 90030-3

David Eppstein
quelle
5
Übrigens, wenn Sie die Single-Source-Version (und in gewisser Weise die All-Pair-Version) des Problems für ungerichtete Graphen lösen möchten, können Sie dies in randomisierter O (m + n) -Zeit tun: TC Hu stellte 1961 fest, dass die Engpasspfade für alle Paare werden in einem Max-Spanning-Tree codiert. Dann erhalten Sie mit Karger, Klein und Tarjans linearem Zeit-Min-Spanning-Tree-Algorithmus das, was Sie wollen.
Virgi
Soweit ich das beurteilen kann ist der Hinweis nicht das was ich brauche. Ein st-Pfad in einem min-max-Spannbaum ist nicht unbedingt ein kürzester st-Pfad mit Engpass. Auch der KKT-Algorithmus für die lineare erwartete Zeit ist nicht das, was ich brauche, da ich eine deterministische, nicht erwartete Laufzeit möchte. Trotzdem danke für die Hilfe.
Ben
4
Tatsächlich hat der st-Pfad P in einem minimalen Spannbaum T ein minimales maximales Kantengewicht über alle st-Pfade. Angenommen, es tut nicht. Dann sei die maximale Kante von P e. Wenn Sie e aus T entfernen, wird der Graph abgeschnitten. Der reale minmax st Pfad P 'muss eine Kante e' haben, die diesen Schnitt kreuzt. Das Hinzufügen von e 'zu T \ {e} erzeugt einen neuen Spannbaum T', der geringere Kosten als T haben muss, da das Gewicht von e 'höchstens das maximale Kantengewicht von P' ist, das kleiner als w (e) ist. Dies widerspricht der Tatsache, dass T ein min Spanning Tree ist.
Virgi