Directing Road Networks by Listing Strong Orientations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Directing Road Networks by Listing Strong Orientations

Résumé

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
Fichier principal
Vignette du fichier
Strong_Orientations.pdf (322.12 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01388476 , version 1 (30-05-2017)

Identifiants

Citer

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⟩

Collections

INRIA INRIA2
97 Consultations
456 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More