Problems on One Way Road Networks

Jammigumpula Ajay ; Avinandan Das ; Binayak Dutta ; Arindam Karmakar ; Sasanka Roy ; Navaneeta Saikia

Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 523-546.

Résumé

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 \ne j)$ occurs if they reach a vertex $v \in 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_{max}\subseteq C$, 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 $\mathcal{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 $\mathcal{O}(1)$ time and the shortest path can be computed in $\mathcal{O}(p)$ time, where $p$ is the number of vertices in the path.

Détail

DOI : 10.7155/jgaa.00544

Keywords: Directed graphs, Independent sets, Traffic configuration, Shortest path