<p>As far as I know, the problem is sometimes called "nondecreasing paths", and was studied since the 50s.
See for instance this paper: G. J. Minty. A Variant on the Shortest-Route Problem, Operations Research, 6(6):882–883, 1958.</p>

<p>The version of the problem which asks for the nondecreasing path from $s$ to $t$ with minimum last edge weight is typically referred to as "earliest arrivals" (since the last edge weight is the arrival time in the itinerary application). There's a lot of work in the literature focusing on this version.</p>

CC BY-SA 3.0
2011-04-11T00:13:59.537Z
2011-04-11T00:13:59.537Z
virgi
<p>Take a directed graph $G$ where the edges are decorated with a a natural  number. We want the set of all paths $P$ between two vertices $v_1$ and $v_2$ such that each successive edge in the path is decorated with a natural number that is greater than the natural number decorating the previous edge. </p>

<p>An application for this would be bus or train schedules. If you're trying to determine the different routes between two cities based on transfers between stations. (You can't take a second train scheduled to leave for before the first one arrives.)</p>

<p>I've informally been calling this a "scheduled graph". But I don't know what the name for this in the literature is.</p>

<p>Any references to algorithms related to this are of interest as well.</p>

CC BY-SA 3.0
2011-04-10T15:59:42.640Z
mildly related: http://cstheory.stackexchange.com/questions/5849/a-possibly-new-representation-of-dags
Artem Kaznatcheev
CC BY-SA 3.0
2011-04-10T16:54:31.670Z
If you consider the line graph of $G$ and oriented the edges from a lower-numbered node to a higher-numbered node, you obtain a DAG $G'$. Conversely, any acyclic orientation of any line graph can be obtained this way. Hence your problem seems to be essentially equal to the following problem: given an acyclic orientation of a line graph, find all directed paths that join a given pair of nodes. But I am not sure if the property of being a line graph really helps here...?
Jukka Suomela
<ds.algorithms><reference-request><graph-algorithms><terminology>
What is the name of this type of directed graph problem?
Rob
# What is the name of this type of directed graph problem?

(Asked by: username_0 on 2011-04-10)

Take a directed graph $G$ where the edges are decorated with a a natural number. We want the set of all paths $P$ between two vertices $v\_1$ and $v\_2$ such that each successive edge in the path is decorated with a natural number that is greater than the natural number decorating the previous edge.

An application for this would be bus or train schedules. If you're trying to determine the different routes between two cities based on transfers between stations. (You can't take a second train scheduled to leave for before the first one arrives.)

I've informally been calling this a "scheduled graph". But I don't know what the name for this in the literature is.

Any references to algorithms related to this are of interest as well.

**Tags:** ds.algorithms, reference-request, graph-algorithms, terminology

> **Comments:**
> **username_1**: mildly related: http://cstheory.stackexchange.com/questions/5849/a-possibly-new-representation-of-dags  
> **username_2**: If you consider the line graph of $G$ and oriented the edges from a lower-numbered node to a higher-numbered node, you obtain a DAG $G'$. Conversely, any acyclic orientation of any line graph can be obtained this way. Hence your problem seems to be essentially equal to the following problem: given an acyclic orientation of a line graph, find all directed paths that join a given pair of nodes. But I am not sure if the property of being a line graph really helps here...?  

---

## 1 answers

### Answer by username_3 on 2011-04-11. Score: 15 | Accepted answer

As far as I know, the problem is sometimes called "nondecreasing paths", and was studied since the 50s.
See for instance this paper: G. J. Minty. A Variant on the Shortest-Route Problem, Operations Research, 6(6):882–883, 1958.

The version of the problem which asks for the nondecreasing path from $s$ to $t$ with minimum last edge weight is typically referred to as "earliest arrivals" (since the last edge weight is the arrival time in the itinerary application). There's a lot of work in the literature focusing on this version.


---

