Approximate distance sensitivity oracles in subquadratic space

DOI10.1145/3564246.3585251MaRDI QIDQ6499311

Shiri Chechik, Sarel Cohen, Keerti Choudhary, Tobias Friedrich, Simon Krogmann, Martin Schirneck, Davide Bilò

Publication date: 8 May 2024

zbMATH Keywords

approximate shortest pathsdistance sensitivity oraclesubquadratic spacefault-tolerant data structure

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(f\)-sensitivity distance oracles and routing schemes
• Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
• Improved distance sensitivity oracles with subcubic preprocessing time
• Deterministic Dictionaries
• Multiple-Source Shortest Paths in Embedded Graphs
• Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
• Replacement paths and k simple shortest paths in unweighted directed graphs
• Faster Replacement Paths and Distance Sensitivity Oracles
• Oracles for Distances Avoiding a Failed Node or Link
• Approximate distance oracles
• (1 + ∊)-Approximate f-Sensitive Distance Oracles
• Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
• Restoration by path concatenation: fast recovery of MPLS paths
• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• A nearly optimal oracle for avoiding failed vertices and edges
• Fault Tolerant Spanners for General Graphs

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