# Item

ITEM ACTIONSEXPORT

Released

Report

#### Efficient computation of implicit representations of sparse graphs (revised version)

##### MPS-Authors

##### External Ressource

No external resources are shared

##### Fulltext (public)

MPI-I-95-1-013.pdf

(Any fulltext), 209KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Arikati, S. R., Maheshwari, A., & Zaroliagis, C.(1995). *Efficient
computation of implicit representations of sparse graphs (revised version)* (MPI-I-1995-1-013). Saarbrücken: Max-Planck-Institut
für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-A704-1

##### 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.