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

Item

ITEM ACTIONSEXPORT

Released

Report

Efficient computation of compact representations of sparse graphs

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-94-148.pdf
(Any fulltext), 149KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Arikati, S. R., Maheshwari, A., & Zaroliagis, C.(1994). Efficient computation of compact representations of sparse graphs (MPI-I-94-148). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B530-E
Abstract
Sparse graphs (e.g.~trees, planar graphs, relative neighborhood graphs) are among the commonly used data-structures in computational geometry. The problem of finding a compact representation for sparse graphs such that vertex adjacency can be tested quickly is fundamental to several geometric and graph algorithms. We provide here simple and optimal algorithms for constructing a compact representation of $O(n)$ size for an $n$-vertex sparse graph such that the adjacency can be tested in $O(1)$ time. Our sequential algorithm runs in $O(n)$ time, while the parallel one runs in $O(\log n)$ time using $O(n/{\log n})$ CRCW PRAM processors. Previous results for this problem are based on matroid partitioning and thus have a high complexity.