Name
Abstract | ||
|---|---|---|
We consider the problem of encoding a graph with n vertices and m edges compactly supporting adjacency, neighborhood and degree queries in constant time in the 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 that it is impossible to achieve the information-theory
lower bound within lower order terms unless the graph is too sparse (namely m = o(n
δ
) for any constant δ> 0) or too dense (namely m = ω(n
2 − δ
) for any constant δ> 0).
Furthermore, we present a succinct encoding for graphs for all values of n,m supporting queries in constant time. The space requirement of the representation is always within a multiplicative 1 + ε factor of the information-theory lower bound for any arbitrarily small constant ε> 0. 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 when the graph is sparse (m = o(n
δ
) for any constant δ> 0).
|
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-87744-8_33 | European Symposium on Algorithms |
Keywords | Field | DocType |
msupporting query,degree query,arbitrary graphs,succinct representations,nand m,constant time,achievable space,space requirement,neighborhood query,adjacency query,lower order term,optimal space requirement,lower bound,information theory | Adjacency list,Discrete mathematics,Combinatorics,Vertex (geometry),Logical matrix,Multiplicative function,Upper and lower bounds,Succinctness,Cell-probe model,Mathematics,Encoding (memory) | Conference |
Volume | ISSN | Citations |
5193 | 0302-9743 | 21 |
PageRank | References | Authors |
0.75 | 14 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arash Farzan | 1 | 136 | 11.07 |
| J. Ian Munro | 2 | 3010 | 462.97 |