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 metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal.inria.fr/hal-01388476
Contributor : Marie-France Sagot <>
Submitted on : Tuesday, May 30, 2017 - 1:50:02 PM
Last modification on : Tuesday, February 26, 2019 - 10:54:02 AM
Long-term archiving on : Wednesday, September 6, 2017 - 1:50:05 PM

File

Strong_Orientations.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

175

Files downloads

142