@techreport{ArikatiMaheshwariZaroliagis95,
TITLE = {Efficient computation of implicit representations of sparse graphs (revised version)},
AUTHOR = {Arikati, Srinivasa R. and Maheshwari, Anil and Zaroliagis, Christos},
LANGUAGE = {eng},
NUMBER = {MPI-I-1995-1-013},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {1995},
DATE = {1995},
ABSTRACT = {The problem of finding an implicit representation for a graph such that vertex adjacency 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 efficiently by providing simple and optimal algorithms, both in a sequential and 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 processors, or in $O(\log n\log^*n)$ time using $O(n/\log n\log^*n)$ EREW PRAM processors. Previous results for this problem are based on matroid partitioning and thus have a high complexity.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}