1-sensitive decremental st-shortest paths (Shortest Path (Directed Graphs))

Description

Determine the st-shortest path with a sensitivity of 1 using decremental techniques.

Related Problems

Generalizations: st-Shortest Path

Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, Second Shortest Simple Path, 1-sensitive (3/2)-approximate ss-shortest paths, 2-sensitive (7/5)-approximate st-shortest paths, 2-sensitive decremental st-shortest paths, Replacement Paths Problem

Parameters

No parameters found.

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions FROM Problem

Problem	Implication	Year	Citation	Reduction
BMM	assume: BMM then: for directed unweighted graphs with $n$ vertices and $m \geq n$ edges require either $m^{1-o({1})}\sqrt{n}$ preprocessing time or $m^{1-o({1})}/\sqrt{n}$ query time for every function $m$ of $n$	2017	https://arxiv.org/pdf/1703.01638.pdf	link
Replacement Paths Problem (RPP)	assume: APSP Hypothesis then: target cannot be solved with preprocessing time $O(n^{3-\epsilon})$ and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in directed weighted graphs	2017	https://arxiv.org/pdf/1703.01638.pdf	link