Referensi untuk algoritma cepat untuk jalur terpendek bottleneck

12

Saya mencari referensi yang baik untuk jalur terpendek bottleneck. Khususnya, mengingat simpul s dan t dalam grafik tidak berarah dengan bobot tepi, Anda ingin jalur terpendek dari s ke t, di mana panjang jalur adalah tepi maksimum di jalur itu. Ini dapat dipecahkan dalam waktu O (n + m) dengan menemukan berat tepi median dan (hati-hati) secara rekursif menghapus setengah tepi.

Adakah yang tahu referensi untuk ini?

ds.algorithms reference-request graph-algorithms Ben
sumber
Mungkin ini adalah titik diperdebatkan, tetapi masalah yang Anda gambarkan adalah masalah jalur minimum. Jalur terpendek bottleneck adalah versi maksimal dari apa yang Anda gambarkan. Algoritme untuk salah satu versi umumnya (selalu?) Menghasilkan algoritma untuk versi lain.
bbejot

Jawaban:

10

PM Camerini (1978), Masalah pohon spanning min-max dan beberapa ekstensi, Information Processing Letters 7 (1): 10–14, doi: 10.1016 / 0020-0190 (78) 90030-3

David Eppstein
sumber
5
Btw, jika Anda ingin menyelesaikan versi single-source (dan dalam arti semua-pasangan) masalah untuk grafik tidak terarah, Anda dapat melakukannya dalam waktu O (m + n) acak: TC Hu mencatat pada tahun 1961 bahwa jalur bottleneck untuk semua pasangan dikodekan dalam pohon spanning max; kemudian algoritma min spanning tree linier Karger, Klein dan Tarjan memberikan apa yang Anda inginkan.
virgi
Sejauh yang saya tahu referensi bukan yang saya butuhkan. Jalur st di pohon spanning min-max tidak perlu jalur bottleneck st paling pendek. Juga, algoritma waktu yang diharapkan linear KKT juga tidak apa yang saya butuhkan, karena saya ingin deterministik tidak diharapkan waktu berjalan. Terima kasih atas bantuannya.
Ben
4
Sebenarnya, jalur st P dalam pohon rentang minimum T memiliki berat tepi maksimum minimum di atas semua jalur st. Misalkan tidak. Kemudian biarkan ujung maksimal P menjadi e. Menghapus e dari T menciptakan potongan grafik. Path minmax st nyata P 'harus memiliki tepi dan melintasi memotong ini. Menambahkan e 'ke T \ {e} menciptakan pohon spanning baru T' yang harus memiliki biaya lebih kecil dari T karena berat e 'paling banyak adalah bobot tepi maksimal pada P' yang kurang dari w (e). Ini bertentangan dengan fakta bahwa T adalah pohon spanning min.
virgi