EFFICIENT COMPUTATION OF IMPLICIT REPRESENTATIONS OF SPARSE GRAPHS

The problem of finding an implicit representation for a graph such tha t vertex adjacency can be tested quickly is fundamental to all graph a lgorithms. In particular, it is possible to represent sparse graphs on n vertices using O(n) space such that vertex adjacency is tested in O (1) time. We show here how to construct such a representation efficien tly by providing simple and optimal algorithms, both in a sequential a nd a parallel setting. Our sequential algorithm runs in O(n) time. The parallel algorithm runs in O(log n) time using O(n/log n) CRCW PRAM p rocessors, or in O(Iog n log n) time using O(nl log n log* n) EREW PR AM processors. Previous results for this problem are based on matroid partitioning and thus have a high complexity.