Énumération à délai constant

par

Luc Segoufin

INRIA et ENS Cachan

Résumé:

L'énumération pour une requête consiste à lister, une par une et sans répétition, les réponses à la requête sur une base de données. Par exemple on pourrait énumérer tous les triangles d'un graphe ou toutes les paires de noeuds à distance deux.

Les algorithmes d'énumération efficaces essayent de minimiser deux paramètres clefs: le temps de précalcul et le délai entre deux solutions consécutives.

Dans cet exposé on va considérer l'énumération à délai constant après un précalcul linéaire. Cela ne peut pas toujours être possible. Il faut des contraintes soit sur la requête soit sur la base de données. Nous allons voir plusieurs scénarios où cela est possible.