Istituto di Scienza e Tecnologie dell'Informazione     
Ferragina P., Nitto I., Venturini R. On compact representations of all-pairs-shortest-path-distance matrices. In: Theoretical Computer Science, vol. 411 (34/36) pp. 3293 - 3300. Elsevier, 2010.
Let G be an unweighted and undirected graph of n nodes, and let be the nn matrix storing the All-Pairs-Shortest-Path Distances in G. Since contains integers in [n] U +∞, its plain storage takes n^2log(n+1) bits. However, a simple counting argument shows that n^2/2 bits are necessary to store . In this paper we investigate the question of finding a succinct representation of 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_2 3. 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.
URL: http://www.sciencedirect.com/science?_ob=PublicationURL&_tockey=%23TOC%235674%232010%23995889965%232197811%23FLP%23&_cdi=5674&_pubType=J&view=c&_auth=y&_acct=C000061181&_version=1&_urlVersion=0&_userid=3967543&md5=d8b311bdfc4e3beb764bc3d251d014d3
DOI: 10.1016/j.tcs.2010.05.021
Subject Succinct Data Structures
Shortest Paths
E.4 Coding and Information Theory
E.1 Data Structures

Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional