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

Description

Determine the st-shortest path with a sensitivity of 2 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, 1-sensitive decremental st-shortest paths, Replacement Paths Problem

Parameters

$V$: number of vertices

$E$: number of edges

$L$: maximum absolute value of edge cost

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions FROM Problem

Problem	Implication	Year	Citation	Reduction
Directed, Weighted APSP	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 undirected weighted graphs	2017	https://arxiv.org/pdf/1703.01638.pdf	link