Succinct Oracles for Exact Distances in Undirected Unweighted Graphs
Paolo Ferragina, Igor Nitto, Rossano Venturini · UnipiEprints Open Archive (Università di Pisa) · 2007
Let G be an unweighted and undirected graph of n nodes, and let D be the n x n matrix storing the All-Pairs-Shortest-Path distances in G. Since D contains integers in [n], its plain storage takes n^2log (n + 1) bits. However, a simple counting argument shows that n^2/2 bits are necessary to store D. In this paper we investigate the question of finding a succinct representation of D that requires O(n^2) bits of storage and still supports constant-time access to each of its entries. This is asymptotically optimal in the worst case, and far from the information-theoretic lower-bound by a multiplicative factor log 3 \\simeq 1.585. As a result O(1) bits per pairs of nodes in G are enough to retain constant-time access to their shortest-path distance. We achieve this result by reducing the storage of D to the succinct storage of labeled trees and ternary sequences, for which we properly adapt and orchestrate the use of known compressed data structures.