|
This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies.
For more information visit Aigaion.nl. | |
Type of publication: | Article |
Entered by: | |
Title | Efficient computation of implicit representations of sparse graphs*1 |
Bibtex cite ID | RACTI-RU1-1997-6 |
Journal | Discrete Applied Mathematics |
Year published | 1997 |
Volume | 78 |
Pages | 1-16 |
Keywords | Implicit representation,Sparse graphs,Arboricity,Graph algorithms,Parallel computation |
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(l) 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 inO(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. |
Authors | |
Topics
| |
BibTeX | BibTeX |
RIS | RIS |
Attachments |
efficient.pdf (main file) |
|
Publication ID | 860 |
|
|