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

From Algorithm Wiki
Revision as of 07:52, 10 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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