Evaluating Relational Expressions with Dense and Sparse Arguments
Thomas G. Szymanski, Jeffrey David Ullman · SIAM Journal on Computing · 1977
We consider expressions whose arguments are relations and whose operators are chosen from among $\cup , \circ ,{}^*$, and ${}^{ - 1}$. We further assume that operands may be designated “sparse” or “dense”, in a manner to be made formal subsequently. Our aim is to determine whether the evaluation of such an expression is (a) as hard as general transitive closure, (b) as hard as transitive closure for sparse graphs, (c) as hard as finding connected components of an undirected graph.