A connected road network with N nodes and L edges has ≤ 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 (2) preprocessing time and space.
Directing road networks by listing strong orientations / Conte Alessio; Grossi Roberto; Marino Andrea; Rizzi Romeo; Versari Luca. - STAMPA. - 9843:(2016), pp. 83-95. (Intervento presentato al convegno 27th International Workshop on Combinatorial Algorithms, IWOCA 2016 tenutosi a fin nel 2016) [10.1007/978-3-319-44543-47].
Directing road networks by listing strong orientations
Grossi Roberto;Marino Andrea;
2016
Abstract
A connected road network with N nodes and L edges has ≤ 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 (2) preprocessing time and space.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
