Evaluating relational expressions with dense and sparse arguments
- 1 October 1975
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We consider expressions whose arguments are relations and whose operators are chosen from among ∪, ο, *, 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 connected components of an undirected graph.Keywords
This publication has 0 references indexed in Scilit: