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

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.
9783319445427
9783319445427
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/848844
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact