Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00544
Problems on One Way Road Networks
Jammigumpula Ajay,
Avinandan Das,
Binayak Dutta,
Arindam Karmakar,
Sasanka Roy, and
Navaneeta Saikia
Vol. 24, no. 3, pp. 523-546, 2020. Regular paper.
Abstract 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.
|
Submitted: July 2019.
Reviewed: October 2019.
Revised: April 2020.
Reviewed: May 2020.
Revised: August 2020.
Accepted: October 2020.
Final: October 2020.
Published: October 2020.
Communicated by
Gill Barequet
|
Journal Supporters
|