Las representaciones más simples para gráficos utilizan matrices / listas de adyacencia, lo que significa que cada nodo y borde se representa explícitamente. La importancia de las representaciones implícitas para gráficos que exhiben fuertes regularidades ha sido reconocida desde hace mucho tiempo. Por ejemplo, Galperin y Wigderson (1983), Papadimitriou y Yannakakis ( Una nota sobre representaciones sucintas de gráficos , 1986) exploraron la cuestión de los gráficos cuya matriz de adyacencia está representada por una fórmula booleana que responde si (i, j) es o no un borde dada la representación binaria de los números de nodo i y j. Bajo algunas restricciones comúnmente satisfechas en las reducciones, los problemas P-completos para gráficos explícitos se vuelven PSPACE-completos para esta representación, los problemas NP-completos se vuelven NEXPTIME-completos, etc.
Un enfoque natural para tales gráficos regulares es representar la fórmula booleana usando un ROBDD; La dificultad es que los algoritmos clásicos tienden a enumerar los nodos uno por uno, lo que incurre en un costo exponencial en dicha representación y, por lo tanto, debe evitarse. Se han publicado artículos sobre problemas clásicos que se resuelven utilizando dicha representación, por ejemplo, Gentilini et al. ( Calcular componentes fuertemente conectados en un número lineal de pasos simbólicos ), Woelfel ( Clasificación topológica simbólica con OBDD ).
Me pregunto si hay alguna encuesta sobre tales técnicas, porque es inconveniente dragar la literatura en el estado del arte ...
fuente