Problems on One Way Road Networks - Ajay, Jammigumpula; Das, Avinandan; Dutta, Binayak; Karmakar, Arindam; Roy, Sasanka; Saikia, Navaneeta (Journal of Graph Algorithms and Applications, 2020)
A One-Way Road Network is an ordered pair OWRN = (W_x,W_y) comprising of a set W_x of m directed horizontal roads along with another set W_y of n directed vertical roads. An OWRN can also be viewed as a directed grid graph GG=(V, E), where V corresponds to intersections between every pair of horizontal and vertical roads, and there is a directed edge between every pair of consecutive vertices in V in the same direction corresponding to that road. A vehicle c is defined as a 3-tuple (t,s,P), where c starts moving at time t and moves with a constant speed s from its start vertex to destination vertex along pre-specified directed path P, unless a collision occurs. A collision between a pair of vehicles c_i and c_j (i e j) occurs if they reach a vertex v V (a junction in OWRN) orthogonally at the same time. A traffic configuration on an OWRN is a 2-tuple TC=( GG, C), where C is a set of vehicles, each travelling on a pre-specified path on GG. A collision-free TC is a traffic configuration without any collision. We prove that finding a maximum cardinality subset C_maxC, such that TC = (GG, C_max) is collision-free, is NP-hard. We also show that GG can be preprocessed into a data-structure in O(n+m) time and space, such that the length of the shortest path between any pair of vertices in GG can be computed in O(1) time and the shortest path can be computed in O(p) time, where p is the number of vertices in the path.