Referencia para el algoritmo rápido para las rutas más cortas del cuello de botella

12

Estoy buscando una buena referencia para los caminos más cortos del cuello de botella. Específicamente, dados los vértices syt en un gráfico no dirigido con pesos de arista, desea la ruta más corta de sa t, donde la longitud de una ruta es la arista máxima en esa ruta. Esto se puede resolver en el tiempo O (n + m) encontrando el peso medio del borde y (cuidadosamente) eliminando recursivamente la mitad de los bordes.

¿Alguien sabe una referencia para esto?

ds.algorithms reference-request graph-algorithms Ben
fuente
Quizás este es un punto discutible, pero el problema que describe es el problema de la ruta minimax. La ruta más corta del cuello de botella es la versión máxima-mínima de lo que usted describe. Sin embargo, un algoritmo para una de las versiones generalmente (¿siempre?) Produce un algoritmo para la otra versión.
bbejot

Respuestas:

10

PM Camerini (1978), The min-max spanning tree problem y algunas extensiones, Information Processing Letters 7 (1): 10–14, doi: 10.1016 / 0020-0190 (78) 90030-3

David Eppstein
fuente
55
Por cierto, si desea resolver la versión del problema de una sola fuente (y, en cierto sentido, todos los pares) para gráficos no dirigidos, puede hacerlo en tiempo aleatorio O (m + n): TC Hu señaló en 1961 que el las rutas de cuello de botella para todos los pares están codificadas en un árbol de expansión máxima; entonces el algoritmo de árbol de expansión de tiempo lineal mínimo de Karger, Klein y Tarjan le brinda lo que desea.
virgi
Por lo que puedo decir, la referencia no es lo que necesito. Un camino st en un árbol de expansión min-max no es necesariamente un camino st más corto de cuello de botella. Además, el algoritmo de tiempo esperado lineal KKT tampoco es lo que necesito, ya que quiero un tiempo de ejecución determinista no esperado. Gracias de todos modos por la ayuda.
Ben
44
En realidad, el camino st P en un árbol de expansión mínimo T tiene un peso mínimo máximo en el borde sobre todos los caminos st. Supongamos que no. Entonces deje que el borde máximo de P sea e. Eliminar e de T crea un corte del gráfico. La trayectoria real minmax st P 'debe tener un borde e' que cruce este corte. Agregar e 'a T \ {e} crea un nuevo árbol de expansión T' que debe tener un costo menor que T ya que el peso de e 'es como máximo el peso máximo del borde en P', que es menor que w (e). Esto contradice el hecho de que T es un árbol de expansión mínima.
virgi