Back to Search
Start Over
Fully dynamic update of arc-flags
- Source :
- Networks. 63:243-259
- Publication Year :
- 2014
- Publisher :
- Wiley, 2014.
-
Abstract
- Best connections in real networks are usually found by applying Dijkstra's shortest paths algorithm. Unfortunately, networks deriving from real-world applications are huge, yielding unsustainable times to compute shortest paths. Therefore, considerable research has been conducted in recent years to accelerate Dijkstra's algorithm on typical instances of transportation and communication networks, such as road networks. These efforts have led to the development of many so called speed-up techniques, as for example Arc-Flags. The main drawback of many of these techniques, including Arc-Flags, is that they do not work well in the realistic dynamic scenarios where the networks change over time. In this article, we introduce a new data structure, named Road-Signs, which is used to update the Arc-Flags of a graph in fully dynamic scenarios. Road-Signs can be used to compute Arc-Flags, can be efficiently updated and does not require large space consumption for sparse networks. We develop a fully dynamic algorithm for updating Arc-Flags, by updating Road-Signs, each time that a modification occurs on an edge of the network. We show that this algorithm is better than recomputation from scratch of Arc-Flags in terms of the affected parameters of the input, which makes this solution suitable to be efficient in practice. However, it is not better than recomputation from scratch in the worst case. We also propose an experimental study to evaluate the practical performance of the new dynamic algorithm. To this aim, we use real-world road networks subject to sequences of weight change operations. Our experiments show a significant speed-up in the updating phase with respect to the recomputation from scratch of Arc-Flags.Copyright © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 633, 243-259 2014
- Subjects :
- Theoretical computer science
Computer Networks and Communications
Computer science
Distributed computing
Weight change
Algorithm engineering
Data structure
Dynamic problem
Hardware and Architecture
Graph (abstract data type)
Enhanced Data Rates for GSM Evolution
Suurballe's algorithm
Dijkstra's algorithm
Software
Information Systems
Subjects
Details
- ISSN :
- 00283045
- Volume :
- 63
- Database :
- OpenAIRE
- Journal :
- Networks
- Accession number :
- edsair.doi...........c22a3d114065e7b78a31eb456314457d
- Full Text :
- https://doi.org/10.1002/net.21542