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.
Directing road networks by listing strong orientations
RIZZI, ROMEO;
2016-01-01
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. © Springer International Publishing Switzerland 2016.File | Dimensione | Formato | |
---|---|---|---|
DirectingRoadNetworksListingOrientations.pdf
solo utenti autorizzati
Tipologia:
Versione dell'editore
Licenza:
Accesso ristretto
Dimensione
256.59 kB
Formato
Adobe PDF
|
256.59 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.