Problems on One Way Road Networks

2016/06/14 by Jammigumpula Ajaykumar, Avinandan Das, Ajaykumar, Jammigumpula +5
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG

paper · pdf · doi:10.48550/arxiv.1606.04334

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

arxiv created 2016/09/10 · arxiv updated 2016/09/13

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⊆ 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.

Related

• Crossing Patterns in Nonplanar Road Networks
• The Complexity of Routing with Few Collisions
• Studying Geometric Graph Properties of Road Networks Through an Algorithmic Lens
• Finding k-shortest paths with limited overlap
• On the Complexity of an Unregulated Traffic Crossing