Muy similar a mi pregunta publicada anteriormente . Esta vez, sin embargo, el gráfico no está dirigido.
Dado
- Un gráfico G no dirigido sin múltiples bordes o bucles,
- Un vértice fuente ,
- Un vértice objetivo ,
- Longitud máxima del camino ,
Busco - A subgrafo de G que contiene cualquier vértice y cualquier borde en G (y sólo aquellos), que son parte de al menos un camino simple de s a t con longitud ≤ l .
Notas:
- No necesito enumerar los caminos.
- Estoy buscando un algoritmo eficiente (tiempo y memoria), ya que necesito ejecutarlo en gráficos muy grandes (10 ^ 8 vértices, 10 ^ 9 bordes).
ds.algorithms
graph-algorithms
shortest-path
Lior Kogan
fuente
fuente
Respuestas:
Bueno, el problema está en después de todo. Mantendré la respuesta anterior, ya que también funciona para el caso dirigido (que es NPC, como se respondió en la otra pregunta), y muestra que es F P T con respecto a l .P FPT l
En el caso no dirigido, es solucionable, determinísticamente a través del flujo de costo mínimo (esto podría no funcionar en las escalas a las que se refiere en la pregunta, pero es mejor que el algoritmo exponencial.
El siguiente procedimiento decidirá si alguna arista debe ser parte del gráfico de salida. Para responder al problema original, simplemente recorra todos los bordes.e=(u,v)∈E
Para crear la red de flujo, haga lo siguiente:
Paso 1: expanda para tener un vértice x e y reemplace e con los bordes ( u , x e ) , ( x e , u ) , ( v , x e ) , ( x e , v ) (se dirigen como un parte de la red de flujo), establezca su costo en 0.e xe e (u,xe), (xe,u),(v,xe),(xe,v)
Paso 5: establezca todas las capacidades en 1.
Análisis:
fuente
Aquí es un mal respuesta: se da salida a algunos vértices que forman parte de caminos no simples de a y que no forman parte de ningún camino simple de a de longitud . La respuesta aún podría ser relevante para la aplicación del autor de la pregunta, así que la dejo aquí.s t s t ≤ℓ
Aquí hay un algoritmo que se ejecuta en el tiempo (y en realidad es más rápido que esto cuando es pequeño).O(|V|+|E|) ℓ
El algoritmo ejecuta una búsqueda BFS desde que termina en profundidad . Este BFS proporciona un conjunto de todos los vértices accesibles desde con una ruta de longitud como máximo , y también calcula las distancias para cada . Luego haría lo mismo desde y obtendría el conjunto y las distancias desde . Finalmente, los vértices que está buscando son exactamente . Los bordes son exactamente esos bordes en (s ℓ Vs s ℓ dist(s,v) v∈Vs t Vt t Vsolution={v:v∈Vs∩Vt,dist(s,v)+dist(t,v)≤ℓ} E[Vsolution] =(v,u)∈E:u,v∈Vsolution )
El tiempo de ejecución de este algoritmo es seguramente porque solo hace dos BFS. Pero el tiempo de ejecución es en realidad que será mucho más pequeño que el tamaño del gráfico cuando el radio acerca a y son pequeñas.O(|V|+|E|) O(|Vs|+|Vt|+|E[Vs]|+|E[Vt]|) ℓ s t
Editar: es probable que haya un algoritmo algo más rápido en la práctica que hace un BFS de y de profundidad única en lugar de . Esto descubre todos los caminos, y luego con un poco de contabilidad puede encontrar todos los vértices. Esto reduce el tiempo de ejecución en una raíz cuadrada para el caso de un gráfico grande de aspecto aleatorio cuando es pequeño.s t ℓ/2 ℓ ℓ
fuente
Esto pretende ser un comentario, pero es demasiado largo para publicarlo como comentario.
También podría estar interesado en llaves de gráfico o emuladores para sus propósitos. Una llave de un gráfico es un subgrafo con pocos bordes, pero distancias aproximadamente preservadas. Un emulador es un gráfico cuyos bordes pueden ser ponderados.G=(V,E) H=(V,E′) H=(V,E′,w)
El mejor resultado para las llaves es bordes y un error aditivo de +6 en las estimaciones de distancia en el gráfico. El mejor resultado para los emuladores es bordes y un error aditivo de +4. Tampoco se sabe si podemos vencer a , incluso si se permite que el error sea pollogarítmico.O(n4/3) O(n4/3) O(n4/3)
Si esto suena útil, puedo intentar desenterrar las construcciones relevantes para usted.
fuente