We consider a station in which several trains might stop at the same track at the same time. The trains might enter and leave the station from both sides, but the arrival and departure times and directions are fixed according to a given time table. The problem is to assign tracks to the trains such that they can enter and leave the station on time without being blocked by any other train. We consider some variation of the problem on linear time tables as well as on cyclic time tables and show how to solve them as a graph coloring problem on special graph classes. One of these classes are the so called circular arc containment graphs for which we give an optimal O(n log n) coloring algorithm.
Track assignment
DI STEFANO, GABRIELE
2007
Abstract
We consider a station in which several trains might stop at the same track at the same time. The trains might enter and leave the station from both sides, but the arrival and departure times and directions are fixed according to a given time table. The problem is to assign tracks to the trains such that they can enter and leave the station on time without being blocked by any other train. We consider some variation of the problem on linear time tables as well as on cyclic time tables and show how to solve them as a graph coloring problem on special graph classes. One of these classes are the so called circular arc containment graphs for which we give an optimal O(n log n) coloring algorithm.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
