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.
Directing road networks by listing strong orientations
CONTE, ALESSIO;GROSSI, ROBERTO
;MARINO, ANDREA;
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
