As representações mais simples para gráficos usam matrizes / listas de adjacência, o que significa que cada nó e aresta é representado explicitamente. A importância de representações implícitas para gráficos que apresentam fortes regularidades é reconhecida há muito tempo. Por exemplo, Galperin e Wigderson (1983), Papadimitriou e Yannakakis ( Uma nota sobre representações sucintas de gráficos , 1986) exploraram a questão de gráficos cuja matriz de adjacência é representada por uma fórmula booleana que responde se (i, j) é uma vantagem dada a representação binária dos números de nós iej. Sob algumas restrições geralmente satisfeitas nas reduções, os problemas de preenchimento P para gráficos explícitos tornam-se completos no PSPACE para esta representação, os problemas completos no NP se tornam NEXPTIME, etc.
Uma abordagem natural para esses gráficos regulares é representar a fórmula booleana usando um ROBDD; a dificuldade é que algoritmos clássicos tendem a enumerar nós um por um, o que implica um custo exponencial em tal representação e, portanto, deve ser evitado. Foram publicados trabalhos sobre problemas clássicos sendo resolvidos usando essa representação, por exemplo, Gentilini et al. ( Computando componentes fortemente conectados em um número linear de etapas simbólicas ), Woelfel ( classificação topológica simbólica com OBDDs ).
Gostaria de saber se existe algum levantamento de tais técnicas, porque é inconveniente arrastar a literatura em tais do estado da arte ...
fonte