17
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ mildly related: cstheory.stackexchange.com/questions/5849/… $\endgroup$
    – Artem Kaznatcheev ♦
    Apr 10, 2011 at 15:59
  • 1
    $\begingroup$ 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...? $\endgroup$
    – Jukka Suomela
    Apr 10, 2011 at 16:54

1 Answer 1

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.