Let $OWRN = \left\langle W_x,W_y \right\rangle$ 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 intersection of the horizontal and vertical roads are the vertices of $OWRN$ and any two consecutive vertices on a road is connected by an edge. In this work, we analyze the problem of collision free Traffic configuration in an $OWRN$. A traffic configuration is a two-tuple $TC=\left\langle OWRN, C\right\rangle$, 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=\left\langle OWRN, C_{sub}\right\rangle$ is collision-free, is NP-hard. Lastly we investigate the properties of connectedness, shortest paths in an $OWRN$.
['Jammigumpula Ajaykumar', 'Avinandan Das', 'Navaneeta Saikia', 'Arindam Karmakar']
Problems on One Way Road Networks