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

• Title not available (Why is that?)
• Title not available (Why is that?)
• A simple storage scheme for strings achieving entropy bounds
• Approximate distance oracles
• Compact oracles for reachability and approximate distances in planar digraphs
• Compressed data structures: Dictionaries and data-aware measures
• Compressed representations of sequences and full-text indexes
• Low redundancy in static dictionaries with constant query time
• Ramsey partitions and proximity data structures
• Rank and select revisited and extended
• Representing trees of higher degree
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Succinct indexes for strings, binary relations and multi-labeled trees
• Succinct representation of balanced parentheses and static trees
• The level ancestor problem simplified
• Ultra-succinct representation of ordered trees

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)