1997-10-21
Efficient computation of implicit representations of sparse graphs
Publication
Publication
Discrete Applied Mathematics , Volume 78 - Issue 1-3 p. 1- 16
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.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1016/S0166-218X(97)00007-3 | |
| Discrete Applied Mathematics | |
| Organisation | Computational Geometry Lab |
|
Arikati, S.R. (Srinivasa R.), Maheshwari, A, & Zaroliagis, C.D. (Christos D.). (1997). Efficient computation of implicit representations of sparse graphs. Discrete Applied Mathematics, 78(1-3), 1–16. doi:10.1016/S0166-218X(97)00007-3
|
|