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

DOI10.1016/J.TCS.2010.05.021zbMATH Open1196.68059OpenAlexW4237696112MaRDI QIDQ986563FDOQ986563

Authors: Paolo Ferragina, Igor Nitto, Rossano Venturini 

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

Recommendations

• On Compact Representations of All-Pairs-Shortest-Path-Distance Matrices
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• All-pairs shortest paths for unweighted undirected graphs in \(o(mn)\) time
• Succinct Representations of Arbitrary Graphs
• Shortest-Path Reconstruction Algorithms

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) Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cites Work

• 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
• 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
• Succinct indexes for strings, binary relations and multi-labeled trees
• Title not available (Why is that?)
• Compact oracles for reachability and approximate distances in planar digraphs
• Rank and select revisited and extended
• Compressed data structures: Dictionaries and data-aware measures
• Low redundancy in static dictionaries with constant query time
• Ultra-succinct representation of ordered trees
• Approximate distance oracles
• Title not available (Why is that?)

Cited In (4)

• A substring-substring LCS data structure
• Compact navigation and distance oracles for graphs with small treewidth
• External matrix multiplication and all-pairs shortest path
• On Compact Representations of All-Pairs-Shortest-Path-Distance Matrices

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q986563)