On compact representations of all-pairs-shortest-path-distance matrices

DOI10.1016/J.TCS.2010.05.021zbMath1196.68059OpenAlexW4237696112MaRDI QIDQ986563

Paolo Ferragina, Rossano Venturini, Igor Nitto

Publication date: 11 August 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.05.021

zbMATH Keywords

succinct data structuresall-pairs-shortest-path distancescompressed indexes for strings and trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items (2)

A substring-substring LCS data structure ⋮ Compact navigation and distance oracles for graphs with small treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The level ancestor problem simplified
• Representing trees of higher degree
• A simple storage scheme for strings achieving entropy bounds
• Ramsey partitions and proximity data structures
• Compressed data structures: Dictionaries and data-aware measures
• Rank and select revisited and extended
• Low Redundancy in Static Dictionaries with Constant Query Time
• Succinct Representation of Balanced Parentheses and Static Trees
• Compressed representations of sequences and full-text indexes
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Approximate distance oracles
• Compact oracles for reachability and approximate distances in planar digraphs

This page was built for publication: On compact representations of all-pairs-shortest-path-distance matrices