de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Efficient computation of compact representations of sparse graphs

MPG-Autoren
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;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-94-148.pdf
(beliebiger Volltext), 149KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B530-E
Zusammenfassung
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.