<p>Let <span class="math-container">$G$</span> be a directed weighted graph. In addition each edge <span class="math-container">$e$</span> has a time-stamp <span class="math-container">$t(e)$</span>.</p>
<p>A <em>route</em> <span class="math-container">$\pi$</span> from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> is a directed walk from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> with increasing time-stamps.</p>
<p>We are also given two sets of vertices <span class="math-container">$S$</span> (source) and <span class="math-container">$T$</span> (destination).</p>
<p>We associate with each route <span class="math-container">$\pi$</span> one of the edges <span class="math-container">$e$</span> with the following properties:</p>
<ol>
<li><p><span class="math-container">$e$</span> belongs to <span class="math-container">$\pi$</span>,</p>
</li>
<li><p>There is no route to <span class="math-container">$e$</span>'s head from any other source <span class="math-container">$s' \in S$</span> with time-stamps smaller than <span class="math-container">$t(e)$</span>,</p>
</li>
<li><p><span class="math-container">$e$</span> has minimum weight among the edges satisfying the conditions in 1 and 2.</p>
</li>
</ol>
<p>Let's the edge corresponding to a route its bottleneck.</p>
<p>Given <span class="math-container">$G$</span>, <span class="math-container">$S$</span>, and <span class="math-container">$T$</span>,
we want to compute the list of bottlenecks for all routes in <span class="math-container">$G$</span> from <span class="math-container">$S$</span> to <span class="math-container">$T$</span>,
i.e. we want a least of the form <span class="math-container">$(s,t,e)$</span> where
<span class="math-container">$s\in S$</span>, <span class="math-container">$t\in T$</span>, and <span class="math-container">$e$</span> is the bottleneck edge for some route from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>.
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.</p>
<h3>Questions</h3>
<p>I am looking for references on algorithms for this or similar problems.</p>
<p>Does this problem have a name?</p>

CC BY-SA 3.0
2013-06-26T09:31:51.197Z
Are the edges or the vertices weighted?
András Salamon
CC BY-SA 3.0
2013-06-26T16:53:28.237Z
I'm not sure it solves your bottleneck problem, but there are some algorithms for this sort of time-monotonic path in "Windows into relational events: data structures for contiguous subsequences of edges", M. J. Bannister, C. DuBois, D. Eppstein, and P. Smyth, SODA 2013, pp. 856-864, arXiv:1209.5791.
David Eppstein
CC BY-SA 3.0
2013-06-26T17:56:58.287Z
@András, the edges.
Kaveh
CC BY-SA 3.0
2013-06-26T19:32:00.183Z
Since the weights are both on the arcs, it seems easier to move to the vertex-weighted line digraph.  One can then intersect the DAG with the poset (actually, transitive tournament) implied by the timestamps.  What remains is a vertex-weighted DAG in which every directed path is a route.  The properties are then about activity-on-node networks (task graphs), and it seems $e$ is a minimum weight vertex among the critical vertices on route $\pi$.
András Salamon
<ds.algorithms><graph-theory>
Bottlenecks in a time-stamped graph
Kaveh
# Bottlenecks in a time-stamped graph

(Asked by: username_0 on 2013-06-26)

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:

1. $e$ belongs to $\pi$,
2. There is no route to $e$'s head from any other source $s' \in S$ with time-stamps smaller than $t(e)$,
3. $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.

### Questions

I am looking for references on algorithms for this or similar problems.

Does this problem have a name?

**Tags:** ds.algorithms, graph-theory
> **Comments:**
> **username_1**: Are the edges or the vertices weighted?  
> **username_2**: I'm not sure it solves your bottleneck problem, but there are some algorithms for this sort of time-monotonic path in "Windows into relational events: data structures for contiguous subsequences of edges", M. J. Bannister, C. DuBois, D. Eppstein, and P. Smyth, SODA 2013, pp. 856-864, arXiv:1209.5791.  
> **username_0**: @András, the edges.  
> **username_1**: Since the weights are both on the arcs, it seems easier to move to the vertex-weighted line digraph.  One can then intersect the DAG with the poset (actually, transitive tournament) implied by the timestamps.  What remains is a vertex-weighted DAG in which every directed path is a route.  The properties are then about activity-on-node networks (task graphs), and it seems $e$ is a minimum weight vertex among the critical vertices on route $\pi$.  

---

## 0 answers

