Accessibilité du DAG avec un espace O (n log n) et des requêtes O (log n) -time?

Pour un graphe orienté acyclique , est - il une structure de données qui permet des requêtes sans nécessiter joignabilité espace quadratique ou le temps linéaire? Idéalement, je recherche un algorithme utilisant uniquement l'espace O (log n) par sommet et le temps logarithmique ${\langle}V,E{\rangle}$ où . $n=|V|+|E|$

Il m'a semblé intuitivement évident qu'une telle structure de données devrait exister, basée sur une généralisation d'algorithmes de tri standard. Mais j'ai été surpris de ne pas en trouver. Tout ce que j'ai rencontré a fait des hypothèses sur le graphique (par exemple, la planarité) ou résolu un problème plus difficile en temps / espace quadratique (par exemple, les requêtes entrelacées avec des modifications du graphique).

La page Wikipedia sur l'accessibilité ne couvre qu'un seul algorithme général (Floyd-Warshall); le reste de la page traite de cas particuliers impliquant des hypothèses comme le graphique étant planaire (ce n'est pas le cas).

Le document le plus souvent cité dans cet espace semble être l' efficacité amortie d'une structure de données de récupération de chemin , mais cela et tous les articles qu'il cite impliquent soit de l'espace O (n ^ 2), soit du temps O (n ^ 2) afin de permettre mises à jour du graphe entrelacé avec les requêtes (ie pas de prétraitement).

Cette question n'a pas reçu de réponse, mais elle traite du problème plus difficile d'autoriser les insertions de bord entrelacées avec les requêtes.

Cette question demandait une structure de données persistante (purement fonctionnelle), qui n'est pas requise ici. Le papier "Succinct Posets" a besoin d'un espace mais il réalise des requêtes temps; Je recherche un algorithme pire temps et meilleur espace. $O(n^2)$ $O(1)$

Recherche principalement un point d'ancrage dans la littérature ici. S'il existe un document d'enquête sur l'accessibilité des graphiques qui ne passe pas 99% de son temps sur le cas du graphique planaire, cela aiderait.

graph-algorithms user4718
la source

Question connexe: cstheory.stackexchange.com/questions/21503/… .

Merci pour le lien RB. Cette question et la première réponse ne traitent pas de l'espace (sauf une brève mention d'une limite d'espace quadratique, qui est ce que cette question cherche à améliorer). La deuxième réponse fait allusion à un résultat négatif pour les requêtes de distance (c'est-à-dire à valeur entière ou réelle) plutôt qu'à l'accessibilité (à savoir {0,1}) qui sont un problème plus facile. Merci quand même!

user4718

Le routage de raccourcis ou les références mentionnées par Christian Sommer à la question connexe peuvent fonctionner dans la pratique. Vous recherchez une approche pratique ou des bornes inférieures théoriques?

András Salamon

n^{2}

$n^2$

u

$u$

v

$v$

Accessibilité du DAG avec un espace O (n log n) et des requêtes O (log n) -time?

Réponses: