Referência para algoritmo rápido para caminhos mais curtos de gargalo

12

Estou procurando uma boa referência para os caminhos mais curtos de gargalo. Especificamente, dados os vértices s e t em um gráfico não direcionado com pesos das arestas, você deseja o caminho mais curto de s a t, em que o comprimento de um caminho é a aresta máxima nesse caminho. Isso pode ser resolvido no tempo O (n + m) localizando o peso médio da aresta e (com cuidado) excluindo recursivamente metade das arestas.

Alguém sabe uma referência para isso?

ds.algorithms reference-request graph-algorithms Ben
fonte
Talvez este seja um ponto discutível, mas o problema que você descreve é ​​o problema do caminho do minimax. O caminho mais curto do gargalo é a versão max-min do que você descreve. Um algoritmo para uma das versões geralmente (sempre?) Gera um algoritmo para a outra versão.
bbejot

Respostas:

10

PM Camerini (1978), O problema da árvore de extensão min-max e algumas extensões, Information Processing Letters 7 (1): 10–14, doi: 10.1016 / 0020-0190 (78) 90030-3

David Eppstein
fonte
5
Aliás, se você quiser resolver a versão de fonte única (e de certa forma os pares) do problema para gráficos não direcionados, poderá fazê-lo em tempo O (m + n) aleatório: TC Hu observou em 1961 que o caminhos de gargalo para todos os pares são codificados em uma árvore de abrangência máxima; então, o algoritmo de tempo mínimo de extensão linear de Karger, Klein e Tarjan fornece o que você deseja.
virgi
Tanto quanto posso dizer, a referência não é o que eu preciso. Um caminho st em uma árvore de extensão min-max não é necessariamente um caminho st mais curto do gargalo. Além disso, o algoritmo linear de tempo esperado da KKT também não é o que eu preciso, pois quero um tempo de execução determinístico e não esperado. Obrigado mesmo assim pela ajuda.
Ben das
4
Na verdade, o percurso P em uma árvore de abrangência mínima T tem um peso máximo mínimo de borda em todos os percursos. Suponha que não. Então deixe a aresta máxima de P ser e. Remover e de T cria um recorte do gráfico. O caminho minmax st real P 'deve ter uma aresta e' cruzando esse corte. Adicionar e 'a T \ {e} cria uma nova árvore de abrangência T', que deve ter um custo menor que T, uma vez que o peso de e 'é no máximo o peso máximo de borda em P' que é menor que w (e). Isso contradiz o fato de que T é uma árvore de abrangência mínima.
virgi