Directing road networks by listing strong orientations

A connected road network with N nodes and L edges has K ≤ 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(m2) preprocessing time and space. © Springer International Publishing Switzerland 2016.