Abstract | ||
---|---|---|
We consider the problem of encoding graphs with n vertices and m edges compactly supporting adjacency, neighborhood and degree queries in constant time in the @Q(logn)-bit word RAM model. The adjacency query asks whether there is an edge between two vertices, the neighborhood query reports the neighbors of a given vertex in constant time per neighbor, and the degree query reports the number of incident edges to a given vertex. We study the problem in the context of succinctness, where the goal is to achieve the optimal space requirement as a function of n and m, to within lower order terms. We prove a lower bound in the cell probe model indicating it is impossible to achieve the information-theory lower bound up to lower order terms unless the graph is either too sparse (namely, m=o(n^@d) for any constant @d0) or too dense (namely m=@w(n^2^-^@d) for any constant @d0). Furthermore, we present a succinct encoding of graphs supporting aforementioned queries in constant time. The space requirement of the encoding is within a multiplicative 1+@e factor of the information-theory lower bound for any arbitrarily small constant @e0. This is the best achievable space bound according to our lower bound where it applies. The space requirement of the representation achieves the information-theory lower bound tightly within lower order terms where the graph is very sparse (m=o(n^@d) for any constant @d0), or very dense (mn^2/lg^1^-^@dn for an arbitrarily small constant @d0). |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.tcs.2013.09.031 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
encoding graph,degree query,constant time,aforementioned query,arbitrary graph,m edge,achievable space,succinct encoding,space requirement,adjacency query,lower order term,optimal space requirement | Journal | 513, |
ISSN | Citations | PageRank |
0304-3975 | 11 | 0.50 |
References | Authors | |
21 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Arash Farzan | 1 | 136 | 11.07 |
J. Ian Munro | 2 | 3010 | 462.97 |