Incremental distance products via faulty shortest paths
From MaRDI portal
Publication:783710
DOI10.1016/j.ipl.2020.105977zbMath1441.68198OpenAlexW3033174434MaRDI QIDQ783710
Publication date: 4 August 2020
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2020.105977
Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
- The k most vital arcs in the shortest path problem
- Finding the most vital node of a shortest path.
- A faster computation of the most vital edge of a shortest path
- 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
- Fast sparse matrix multiplication
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Oracles for Distances Avoiding a Failed Node or Link
- f-Sensitivity Distance Oracles and Routing Schemes
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- (1 + ∊)-Approximate f-Sensitive Distance Oracles
- Multiple-edge-fault-tolerant approximate shortest-path trees
- Compact and Fast Sensitivity Oracles for Single-Source Distances
- Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
- A nearly optimal oracle for avoiding failed vertices and edges
- Near Optimal Algorithms For The Single Source Replacement Paths Problem
- Automata, Languages and Programming
This page was built for publication: Incremental distance products via faulty shortest paths
