Compact distance oracles with large sensitivity and low stretch

DOI10.1007/978-3-031-38906-1_11arXiv2304.14184MaRDI QIDQ6179407

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

Publication date: 16 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2304.14184

zbMATH Keywords

spannerapproximate shortest pathsdistance sensitivity oraclesubquadratic spacefault-tolerant data structure

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Cites Work

• 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
• Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
• Approximate Distance Oracles with Improved Bounds
• Novel Polynomial Basis With Fast Fourier Transform and Its Application to Reed–Solomon Erasure Codes
• Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs
• 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
• Approximate distance oracles with constant query time
• Fault Tolerant Spanners for General Graphs
• Automata, Languages and Programming
• Maintaining exact distances under multiple edge failures

This page was built for publication: Compact distance oracles with large sensitivity and low stretch