Skip to Main content Skip to Navigation
Conference papers

Directing Road Networks by Listing Strong Orientations

Abstract : 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
Document type :
Conference papers
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Tuesday, May 30, 2017 - 1:50:02 PM
Last modification on : Tuesday, May 25, 2021 - 11:46:03 AM
Long-term archiving on: : Wednesday, September 6, 2017 - 1:50:05 PM


Files produced by the author(s)




Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, Luca Versari. Directing Road Networks by Listing Strong Orientations. Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Aug 2016, Helsinki, Finland. ⟨10.1007/978-3-319-44543-4_7⟩. ⟨hal-01388476⟩



Record views


Files downloads