On compact representations of all-pairs-shortest-path-distance matrices (Articolo in rivista)

Type
Label
  • On compact representations of all-pairs-shortest-path-distance matrices (Articolo in rivista) (literal)
Anno
  • 2010-01-01T00:00:00+01:00 (literal)
Alternative label
  • Ferragina P.; Nitto I.; Venturini R. (2010)
    On compact representations of all-pairs-shortest-path-distance matrices
    in Theoretical computer science
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Ferragina P.; Nitto I.; Venturini R. (literal)
Pagina inizio
  • 3293 (literal)
Pagina fine
  • 3300 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 411 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note
  • In: Theoretical Computer Science, vol. 411 (34/36) pp. 3293 - 3300. Elsevier, 2010. (literal)
Note
  • ISI Web of Science (WOS) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Dipartimento di Informatica, Università di Pisa, CNR-ISTI, Pisa (literal)
Titolo
  • On compact representations of all-pairs-shortest-path-distance matrices (literal)
Abstract
  • 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] U +∞, its plain storage takes n. log(n+1) bits. However, a simple counting argument shows that n. /2 bits are necessary to store . In this paper we investigate the question of finding a succinct representation of that requires O(n. ) 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. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it