On compact representations of All-Pairs-Shortest-Path-Distance matrices

Let G be an unweighted and undirected graph of n nodes, and let be the n×n matrix storing the All-Pairs-Shortest-Path Distances in G. Since contains integers in [n]∪+∞, its plain storage takes n2log(n+1) bits. However, a simple counting argument shows that n2/2 bits are necessary to store . In this paper we investigate the question of finding a succinct representation of that requires O(n2) 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 log23≃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 to the succinct storage of labeled trees and ternary sequences, for which we properly adapt and orchestrate the use of known compressed data structures. This approach can be easily and optimally extended to graphs whose edge weights are positive integers bounded by a constant value.