Die einfachsten Darstellungen für Diagramme verwenden Adjazenzmatrizen / -listen, was bedeutet, dass jeder Knoten und jede Kante explizit dargestellt wird. Die Bedeutung impliziter Darstellungen für Diagramme mit starken Regelmäßigkeiten ist seit langem bekannt. Zum Beispiel untersuchten Galperin & Wigderson (1983), Papadimitriou & Yannakakis ( Eine Anmerkung zu prägnanten Darstellungen von Graphen , 1986) die Frage von Graphen, deren Adjazenzmatrix durch eine Boolesche Formel dargestellt wird, die beantwortet, ob (i, j) eine Kante ist oder nicht gegeben die binäre Darstellung der Knotennummern i und j. Unter einigen allgemein erfüllten Einschränkungen für Reduzierungen werden P-vollständige Probleme für explizite Graphen für diese Darstellung PSPACE-vollständig, NP-vollständige Probleme werden NEXPTIME-vollständig usw.
Ein natürlicher Ansatz für solche regulären Graphen besteht darin, die Boolesche Formel unter Verwendung eines ROBDD darzustellen. Die Schwierigkeit besteht darin, dass klassische Algorithmen dazu neigen, Knoten einzeln aufzulisten, was bei einer solchen Darstellung exponentielle Kosten verursacht und daher vermieden werden muss. Es wurden Artikel über klassische Probleme veröffentlicht, die mit einer solchen Darstellung gelöst werden, z. B. Gentilini et al. ( Berechnung stark verbundener Komponenten in einer linearen Anzahl symbolischer Schritte ), Woelfel ( Symbolische topologische Sortierung mit OBDDs ).
Ich frage mich, ob es einen Überblick über solche Techniken gibt, weil es unpraktisch ist, die Literatur auf dem neuesten Stand der Technik auszubaggern ...
quelle