f-sensitivity distance oracles and routing schemes

DOI10.1007/978-3-642-15775-2_8MaRDI QIDQ3586453zbMATH OpenOpenAlexFDO

Authors Shiri Chechik, Michael Langberg, Liam Roditty, David Peleg

Publication date 6 September 2010

Published in Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15775-2_8

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Recommendations

• \(f\)-sensitivity distance oracles and routing schemes
• \((1 + \epsilon)\)-approximate \(f\)-sensitive distance oracles
• A nearly optimal oracle for avoiding failed vertices and edges
• Compact and fast sensitivity oracles for single-source distances
• Oracles for Distances Avoiding a Failed Node or Link

Cited in

(10)

• \(f\)-sensitivity distance oracles and routing schemes
• Fault-Tolerant Compact Routing Schemes for General Graphs
• Improved purely additive fault-tolerant spanners
• Incremental distance products via faulty shortest paths
• Fault-tolerant approximate shortest-path trees
• Compact and fast sensitivity oracles for single-source distances
• \((1 + \epsilon)\)-approximate \(f\)-sensitive distance oracles
• Oracles for Distances Avoiding a Failed Node or Link
• Path-fault-tolerant approximate shortest-path trees
• Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs

This page was built for publication: \(f\)-sensitivity distance oracles and routing schemes

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