Here below the abstract of our new paper “Directing Road Networks by Listing Strong Orientations” presented at IWOCA2016.
A connected road network with N nodes and L edges has K \leq L edges identified as one-way roads. In a feasible direction, these one-way roads are assigned a direction each, so that every node can reach any other [Robbins ’39]. Using O(L) preprocessing time and space usage, it is shown that all feasible directions can be found in O(K) amortized time each.
To do so, we give a new algorithm that lists all the strong orientations of an undirected connected graph with $m$ edges in O(m) amortized time each, using O(m) space.
The cost can be deamortized to obtain O(m) delay with O(m^2) preprocessing time and space.
Thanks to my coauthors: Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, and Luca Versari