¿Accesibilidad DAG con espacio O (n log n) y consultas O (log n) -time?

Para un gráfico acíclico dirigido , hay una estructura de datos que permite consultas de accesibilidad sin requerir espacio cuadrática o tiempo lineal? Idealmente, busco un algoritmo que use solo espacio O (log n) por vértice y tiempo logarítmico ${\langle}V,E{\rangle}$ donde . $n=|V|+|E|$

Me pareció intuitivamente obvio que debería existir una estructura de datos como esta, basada en alguna generalización de algoritmos de clasificación estándar. Pero me sorprendió no poder encontrar ninguno. Todo lo que encontré hizo suposiciones sobre el gráfico (por ejemplo, planaridad) o resolvió un problema más difícil en tiempo / espacio cuadrático (por ejemplo, consultas intercaladas con modificaciones en el gráfico).

La página de Wikipedia sobre Accesibilidad solo cubre un algoritmo general (Floyd-Warshall); el resto de la página trata casos especiales que implican suposiciones como que el gráfico es plano (no lo es).

El artículo más comúnmente citado en este espacio parece ser la eficiencia amortizada de una estructura de datos de recuperación de ruta , pero este y todos los documentos que cita involucran espacio O (n ^ 2) u otro tiempo O (n ^ 2) para permitir actualizaciones al gráfico entrelazado con las consultas (es decir, sin preprocesamiento).

Esta pregunta no fue respondida, pero trata el problema más difícil de permitir inserciones de borde intercaladas con consultas.

Esta pregunta solicitó una estructura de datos persistente (puramente funcional), que no se requiere aquí. El documento "Succinct Posets" necesita espacio pero logra consultas de tiempo ; Busco un algoritmo de peor tiempo y mejor espacio. $O(n^2)$ $O(1)$

Principalmente buscando un punto de apoyo en la literatura aquí. Si hay un documento de encuesta sobre accesibilidad gráfica que no pasa el 99% de su tiempo en el caso de gráfico plano, eso ayudaría.

graph-algorithms usuario4718
fuente

Pregunta relacionada: cstheory.stackexchange.com/questions/21503/… .

Gracias por el enlace RB. Esa pregunta y la primera respuesta no abordan el espacio (excepto una breve mención de un límite de espacio cuadrático, que es en lo que esta pregunta busca una mejora). La segunda respuesta alude a un resultado negativo para las consultas de distancia (es decir, con valor entero o con valor real) en lugar de la posibilidad de alcance (es decir, {0,1} -valorado), que son un problema más fácil. Gracias, sin embargo!

usuario4718

La ruta de acceso directo, o las referencias mencionadas por Christian Sommer en la pregunta relacionada, podrían funcionar en la práctica. ¿Está buscando un enfoque práctico o límites inferiores teóricos?

András Salamon

n^{2}

$n^2$

u

$u$

v

$v$

¿Accesibilidad DAG con espacio O (n log n) y consultas O (log n) -time?

Respuestas: