Optimality conjecture for serial and parallel clique-complex construction algorithms

Let $G$ be a graph and let $k$ be a nonnegative integer. Consider the serial algorithm and parallel algorithm for constructing the $k$-skeleta of the clique complex of $G$ described in the paper. Optimality conjecture. These algorithms are optimal serial and parallel algorithms, respectively, for constructing the $k$-skeleta of the clique complex of a graph. The exact notion of optimality is left open: it may refer to worst-case complexity, average complexity for particular random graph models, or practical performance on real examples.