10
$\begingroup$

The simplest representations for graphs use adjacency matrices/lists, meaning that each node and edge is explicitly represented. The importance of implicit representations for graphs exhibiting strong regularities has long been recognized. For instance, Galperin & Wigderson (1983), Papadimitriou & Yannakakis (A Note on Succinct Representations of Graphs, 1986) explored the question of graphs whose adjacency matrix is represented by a Boolean formula answering whether or not (i,j) is an edge given the binary representation of the node numbers i and j. Under some commonly satisfied constraints on reductions, P-complete problems for explicit graphs become PSPACE-complete for this representation, NP-complete problems become NEXPTIME-complete, etc.

A natural approach to such regular graphs is to represent the Boolean formula using a ROBDD; the difficulty is that classical algorithms tend to enumerate nodes one by one, which incurs exponential cost on such a representation and thus is to be avoided. There have been papers published on classical problems being solved using such a representation, e.g. Gentilini et al. (Computing strongly connected components in a linear number of symbolic steps), Woelfel (Symbolic topological sorting with OBDDs).

I'm wondering whether there is some survey of such techniques, because it's inconvenient to dredge the literature in such of the state of the art...

$\endgroup$
1
$\begingroup$

You may find this link is useful. http://www.andrew.cmu.edu/user/vanhoeve/mdd/

$\endgroup$
  • $\begingroup$ Sometimes links die without being indexed by archive.org. Could you edit to add a brief summary of the linked information? $\endgroup$ – Peter Taylor Aug 14 '18 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.