Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Blelloch, Guy E.
Farzan, Arash

dblp
dblp

Not MPG Author(s):

Blelloch, Guy E.

Editor(s):

Amir, Amihood
Parida, Laxmi

dblp
dblp

Not MPII Editor(s):

Amir, Amihood
Parida, Laxmi

BibTeX cite key*:

Farzan2010a

Title, Booktitle

Title*:

Succinct Representations of Separable Graphs

Booktitle*:

Combinatorial Pattern Matching : 21st Annual Symposium, CPM 2010

Event, URLs

URL of the conference:


URL for downloading the paper:

http://dx.doi.org/10.1007/978-3-642-13509-5_13

Event Address*:

New York, NY

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

12 January 2010

Event End Date:

12 January 2011

Publisher

Name*:

Springer

URL:


Address*:

Berlin

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

6129

Number:


Month:


Pages:

138-150

Year*:

2010

VG Wort Pages:


ISBN/ISSN:

978-3-642-13508-8

Sequence Number:


DOI:

10.1007/978-3-642-13509-5_13



Note, Abstract, ©


(LaTeX) Abstract:

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).



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Farzan2010a,
AUTHOR = {Blelloch, Guy E. and Farzan, Arash},
EDITOR = {Amir, Amihood and Parida, Laxmi},
TITLE = {Succinct Representations of Separable Graphs},
BOOKTITLE = {Combinatorial Pattern Matching : 21st Annual Symposium, CPM 2010},
PUBLISHER = {Springer},
YEAR = {2010},
VOLUME = {6129},
PAGES = {138--150},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {New York, NY},
ISBN = {978-3-642-13508-8},
DOI = {10.1007/978-3-642-13509-5_13},
}


Entry last modified by Anja Becker, 01/18/2011
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/12/2011 01:17:27 AM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Anja Becker
Arash Farzan

Edit Dates
18.01.2011 14:12:07
13.01.2011 13:21:45
01/12/2011 01:17:27 AM

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section