Carleton University
Technical Report TR-95-13
May 1995
Efficient Computation of Implicit Representations of Sparse Graph
Abstract
The problem of nding an implicit representation for a graph such that vertex ad- jacency can be tested quickly is fundamental to all graph algorithms. 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 eciently by providing simple and optimal algorithms, both in a sequential and a par- allel setting. Our sequential algorithm runs in O(n) time. The parallel algorithm runs in O(logn) time using O(n=logn) CRCW PRAM processors, or in O(logn log n) time using O(n= logn log n) EREW PRAM processors. Previous results for this problem are based on matroid partitioning and thus have a high complexity.