Publication Date:
2020-11-16
Description:
We present a graph theoretical model for scheduling trains on a single unidirectional track between two stations. The set of departures of all possible train types at all possible (discrete) points of time is turned into an undirected graph $\Gneu$ by joining two nodes if the corresponding departures are in conflict. This graph $\Gneu$ has no odd antiholes and no $k$-holes for any integer $k\geq 5$. In particular, any finite, node induced subgraph of $\Gneu$ is perfect. For any integer $r\geq 2$ we construct minimal headways for $r$ train types so that the resulting graph $\Gneu$ has $2r$-antiholes and $4$-holes at the same time. Hence, $\Gneu$ is neither a chordal graph nor the complement of a chordal graph, in general. At the end we analyse the maximal cliques in $G$.
Keywords:
ddc:000
Language:
English
Type:
reportzib
,
doc-type:preprint
Format:
application/postscript
Format:
application/pdf
