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
Type de document :
Communication dans un congrès
Veli Mäkinen ; Simon J. Puglisi ; Leena Salmela. Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Aug 2016, Helsinki, Finland. Springer, 9843, 2016, Lecture Notes in Computer Science. 〈10.1007/978-3-319-44543-4_7〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01388476
Contributeur : Marie-France Sagot <>
Soumis le : mardi 30 mai 2017 - 13:50:02
Dernière modification le : mercredi 31 mai 2017 - 01:08:00
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 13:50:05

Fichier

Strong_Orientations.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, Luca Versari. Directing Road Networks by Listing Strong Orientations. Veli Mäkinen ; Simon J. Puglisi ; Leena Salmela. Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Aug 2016, Helsinki, Finland. Springer, 9843, 2016, Lecture Notes in Computer Science. 〈10.1007/978-3-319-44543-4_7〉. 〈hal-01388476〉

Partager

Métriques

Consultations de la notice

81

Téléchargements de fichiers

18