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

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

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)