de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

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

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44027

Arikati,  Srinivasa R.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44968

Maheshwari,  Anil
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45787

Zaroliagis,  Christos
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
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.