Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Succinct Representations of Separable Graphs

Blelloch, G. E., & Farzan, A. (2010). Succinct Representations of Separable Graphs. In A. Amir, & L. Parida (Eds.), Combinatorial Pattern Matching (pp. 138-150). Berlin: Springer. doi:10.1007/978-3-642-13509-5_13.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-16F5-4 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-28AD-5
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Blelloch, Guy E.1, Autor
Farzan, Arash2, Autor           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We consider the problem of highly space-efficient representation of separable graphs while supporting queries in constant time in the RAM with logarithmic word size. In particular, we show constant-time support for adjacency, degree and neighborhood queries. For any monotone class of separable graphs, the storage requirement of the representation is optimal to within lower order terms. Separable graphs are those that admit a $O(n^c)$-separator theorem where $c < 1$. Many graphs that arise in practice are indeed separable. For instance, graphs with a bounded genus are separable. In particular, planar graphs (genus $0$) are separable and our scheme gives the first succinct representation of planar graphs with a storage requirement that matches the information-theory minimum to within lower order terms with constant time support for the queries. We, furthers, show that we can also modify the scheme to succinctly represent the combinatorial planar embedding of planar graphs (and hence encode planar maps).

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20102010
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 536766
DOI: 10.1007/978-3-642-13509-5_13
URI: http://dx.doi.org/10.1007/978-3-642-13509-5_13
Anderer: Local-ID: C1256428004B93B8-D6865F434DFCB112C1257816000198FF-Farzan2010a
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 21st Annual Symposium on Combinatorial Pattern Matching
Veranstaltungsort: New York, NY
Start-/Enddatum: 2010-01-12 - 2011-01-12

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Combinatorial Pattern Matching
  Kurztitel : CPM 2010
  Untertitel : 21st Annual Symposium, CPM 2010
Genre der Quelle: Konferenzband
 Urheber:
Amir, Amihood1, Herausgeber
Parida, Laxmi1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 138 - 150 Identifikator: ISBN: 978-3-642-13508-8

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 6129 Artikelnummer: - Start- / Endseite: - Identifikator: -