Approximate distance sensitivity oracles in subquadratic space

DOI10.46298/THEORETICS.24.15MaRDI QIDQ6566476FDOQ6566476

Authors D. Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, Martin Schirneck

Publication date 3 July 2024

Published in TheoretiCS (Search for Journal in Brave)

zbMATH Keywords

data structuresshortest pathsfault tolerancedistance sensitivity oraclessubquadratic space

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• scientific article; zbMATH DE number 5764802 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 1775403 (Why is no real title available?)
• scientific article; zbMATH DE number 2119745 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• scientific article; zbMATH DE number 7646025 (Why is no real title available?)
• scientific article; zbMATH DE number 7740873 (Why is no real title available?)
• scientific article; zbMATH DE number 7788512 (Why is no real title available?)
• scientific article; zbMATH DE number 7724191 (Why is no real title available?)
• A nearly optimal oracle for avoiding failed vertices and edges
• Approximate distance oracles
• Approximate distance sensitivity oracles in subquadratic space
• Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
• Compact distance oracles with large sensitivity and low stretch
• Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
• Deterministic dictionaries
• Deterministic replacement path covering
• Deterministic sensitivity oracles for diameter, eccentricities and all pairs distances
• Distance Oracles for Stretch Less Than 2
• Distance oracles beyond the Thorup-Zwick bound
• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• Dual-failure distance and connectivity oracles
• Faster replacement paths and distance sensitivity oracles
• Fault tolerant spanners for general graphs
• Improved distance sensitivity oracles with subcubic preprocessing time
• Maintaining exact distances under multiple edge failures
• Multiple-source shortest paths in embedded graphs
• On approximate distance labels and routing schemes with affine stretch
• Oracles for Distances Avoiding a Failed Node or Link
• Partially optimal edge fault-tolerant spanners
• Replacement paths and \(k\) simple shortest paths in unweighted directed graphs
• Replacement paths and distance sensitivity oracles via fast matrix multiplication
• Restoration by path concatenation: fast recovery of MPLS paths
• The space-stretch-time tradeoff in distance oracles
• \((1 + \epsilon)\)-approximate \(f\)-sensitive distance oracles
• \(f\)-sensitivity distance oracles and routing schemes

This page was built for publication: Approximate distance sensitivity oracles in subquadratic space

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