Problems on One Way Road Networks

Abstract

Let $OWRN=⟨W_x,W_y⟩$ be a One Way Road Network where $W_x$ and $W_y$ are the sets of directed horizontal and vertical roads respectively. $OWRN$ can be considered as a variation of directed grid graph. The intersections of the horizontal and vertical roads are the vertices of $OWRN$ and any two consecutive vertices on a road are connected by an edge. In this work, we analyze the problem of collision free traffic configuration in a $OWRN$. A traffic configuration is a two-tuple $TC=⟨OWRN,C⟩$, where $C$ is a set of cars travelling on a pre-defined path. We prove that finding a maximum cardinality subset $C_{sub}\subseteq C$ such that $TC=⟨OWRN,C_{sub}⟩$ is collision-free, is NP-hard. Lastly we investigate the properties of connectedness, shortest paths in a $OWRN$.

5 pages. 4figures, In Proceedings of the 28th Canadian Conference on Computational Geometry, pages 303-308, 2016