Let $G$ be a directed weighted graph. In addition each edge $e$ has a time-stamp $t(e)$.A route $\pi$ from $s$ to $t$ is a directed walk from $s$ to $t$ with increasing time-stamps.We are also given two sets of vertices $S$ (source) and $T$ (destination).We associate with each route $\pi$ one of the edges $e$ with the following properties:$e$ belongs to $\pi$,There is no route to $e$'s head from any other source $s' \in S$ with time-stamps smaller than $t(e)$,$e$ has minimum weight among the edges satisfying the conditions in 1 and 2.Let's the edge corresponding to a route its bottleneck.Given $G$, $S$, and $T$, we want to compute the list of bottlenecks for all routes in $G$ from $S$ to $T$, i.e. we want a least of the form $(s,t,e)$ where $s\in S$, $t\in T$, and $e$ is the bottleneck edge for some route from $s$ to $t$.We don't need all possible bottlenecks for a route but just one of them, and it is better if the set of bottlenecks we get is minimal.QuestionsI am looking for references on algorithms for this or similar problems.Does this problem have a name?
Bottlenecks in a time-stamped graph
ds.algorithms;graph theory