Les représentations les plus simples pour les graphiques utilisent des matrices / listes d'adjacence, ce qui signifie que chaque nœud et bord est explicitement représenté. L'importance des représentations implicites pour les graphiques présentant de fortes régularités est reconnue depuis longtemps. Par exemple, Galperin & Wigderson (1983), Papadimitriou & Yannakakis ( A Note on Succinct Representations of Graphs , 1986) ont exploré la question des graphiques dont la matrice d'adjacence est représentée par une formule booléenne répondant si oui ou non (i, j) est un bord étant donné la représentation binaire des numéros de nœuds i et j. Sous certaines contraintes généralement satisfaites sur les réductions, les problèmes P-complet pour les graphiques explicites deviennent PSPACE-complet pour cette représentation, les problèmes NP-complet deviennent NEXPTIME-complet, etc.
Une approche naturelle de ces graphiques réguliers consiste à représenter la formule booléenne à l'aide d'un ROBDD; la difficulté est que les algorithmes classiques tendent à énumérer les nœuds un par un, ce qui engendre un coût exponentiel sur une telle représentation et est donc à éviter. Des articles ont été publiés sur la résolution de problèmes classiques à l'aide d'une telle représentation, par exemple Gentilini et al. ( Calcul de composants fortement connectés en un nombre linéaire d'étapes symboliques ), Woelfel ( Tri topologique symbolique avec OBDD ).
Je me demande s'il y a un aperçu de ces techniques, car il n'est pas pratique de draguer la littérature dans un état de l'art ...
la source