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

17

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 emV,E 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 O ( 1 ) ; Eu procuro um algoritmo de pior tempo e melhor espaço.O(n2)O(1 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.

user4718
fonte
11
Pergunta relacionada: cstheory.stackexchange.com/questions/21503/… .
RB
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
6
n2vocêv

Respostas:

3

Veja "etiquetagem por intervalo" e "etiquetagem com 2 saltos", aparentemente bastante eficientes na prática, tanto no tempo quanto no espaço, e podem dar o que você deseja. Em geral, existem vários esquemas de "indexação de acessibilidade" para DAGs.

jkff
fonte