Alcançabilidade do DAG com espaço O (n log n) e consultas O (log n) em tempo?

Para um grafo orientado acíclico , existe uma estrutura de dados que permite a consultas de acessibilidade sem a necessidade de espaço quadrática ou tempo linear? Idealmente, procuro um algoritmo usando apenas O (log n) de espaço por vértice e tempo logarítmico em ${\langle}V,E{\rangle}$ que . $n=|V|+|E|$

Pareceu-me intuitivamente óbvio que uma estrutura de dados como essa deveria existir, com base em alguma generalização de algoritmos de classificação padrão. Mas fiquei surpresa por não encontrar nenhuma. Tudo o que encontrei fez suposições sobre o gráfico (por exemplo, planaridade) ou resolveu um problema mais difícil no tempo / espaço quadrático (por exemplo, consultas intercaladas com modificações no gráfico).

A página da Wikipedia sobre acessibilidade abrange apenas um algoritmo geral (Floyd-Warshall); o restante da página lida com casos especiais que envolvem suposições como o gráfico sendo plano (não é).

O trabalho mais citado nesse espaço parece ser a eficiência amortizada de uma estrutura de dados de recuperação de caminho , mas esse e todos os trabalhos que ele cita envolvem espaço O (n ^ 2) ou tempo O (n ^ 2) para permitir atualizações no gráfico intercaladas com as consultas (ou seja, sem pré-processamento).

Esta pergunta não foi respondida, mas lida com o problema mais difícil de permitir inserções de arestas intercaladas com consultas.

Esta pergunta solicitou uma estrutura de dados persistente (funcional), que não é necessária aqui. O documento "Posições sucintas" precisa de espaço , mas obtém consultas em tempo ; Eu procuro um algoritmo de pior tempo e melhor espaço. $O(n^2)$ $O(1)$

Principalmente procurando uma posição na literatura aqui. Se houver um documento de pesquisa sobre acessibilidade de gráficos que não gaste 99% de seu tempo no caso de gráficos planares, isso ajudaria.

graph-algorithms user4718
fonte

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

Obrigado pelo link RB. Essa pergunta e a primeira resposta não tratam do espaço (exceto uma breve menção de um limite quadrático-espacial, que é o que essa pergunta busca melhorar). A segunda resposta alude a um resultado negativo para consultas à distância (ou seja, com valor inteiro ou valor real), em vez de alcançabilidade (ou seja, com valor {0,1}), que são um problema mais fácil. Obrigado, no entanto!

user4718

O roteamento de atalho ou as referências mencionadas por Christian Sommer na pergunta relacionada podem funcionar na prática. Você está procurando uma abordagem prática ou limites teóricos mais baixos?

András Salamon

n^{2}

$n^2$

u

$u$

v

$v$

Alcançabilidade do DAG com espaço O (n log n) e consultas O (log n) em tempo?

Respostas: