Top

Published in:

2014 | OriginalPaper | Chapter

Large Graphs: Fast Cost Update and Query Algorithms. Application for Emergency Vehicles

Author : Ion Cozac

Published in: Advanced Intelligent Computational Technologies and Decision Support Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This chapter presents a method that can be used to solve the shortest path problem in large graphs, together with arc cost updates. Our approach uses a contracted graph, which is obtained from the important nodes of the original graph. Every non-important vertex has one or more assigned important nodes as references. A reference node will help us to quickly find the arcs to be updated. The advantage of our method is that we can quickly update the contracted graph, so it can be safely used for future queries. An application of these algorithms can be used by emergency vehicles.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Recognition Algorithm and Some Optimization Problems on Weakly Quasi-Threshold Graphs

next chapter Scan Converting OCT Images Using Fourier Analysis

Dijkstra, E.W.: A note on two problems ion connection with graphs. Numer. Math. 1, 269–271 (1959)MathSciNetCrossRefMATH

Bauer, R., Delling, D., Wagner, D.: Experimental study of speed-up techniques for timetable information systems. J. Netw. 57, 38–52 (2011)MathSciNetCrossRef

Hart, P.E., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4, 100–107 (1968)CrossRef

Goldberg, A., Harelson, C.: Computing the shortest path: A* search meets graph theory. In: Proceedings of 16th Annual ACM-SIAM Symposium Discrete Algorithms (SODA’05), pp. 156–165 (2005)

Delling, D., Wagner, D.: Landmark-based routing in dynamic graphs. In: Proceedings of 6th Workshop of Experimental Algorithms, Lecture Notes in Computer Science, vol. 4525, pp. 52–65. Springer, June 2007

Möhring, R.H., Schilling, H., Schiltz, B., Wagner, D., Willhalm, T.: Partitioning graphs to speed up Dijkstra’s algorithm. In: Proceedings of 4th Workshop on Experimental Algorithms (WEA’05), Lecture Notes in Computer Science, vol. 3503, pp. 189–202. Springer, 2005

Bauer, R., Delling, D.: SHARC: fast and robust unidirectional routing. In: Proceedings of 10th Workshop of Algorithms and Engineering Experiments (ALENEX’08), SIAM, pp. 13–26 April 2008

Sanders, P., Schultes, D.: Engineering highway hierarchies. In: Proceedings of 14th Annual European Symposium Algorithms (ESA’06), Lecture Notes in Computer Science, vol. 4168, pp. 804–816. Springer, 2006

Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: Proceedings of 7th Workshop Experimental Algorithms, pp. 319–333 (2008)

10.

Goldberg, A., Kaplan, H., Werneck, R.F.: Reach for A*: efficient point-to-point shortest path algorithms. In: Proceedings of the 8th Workshop on Algorithms Engineering and Experiments (ALENEX’06), SIAM, pp. 129–143 (2006)

11.

Gutman, R.J.: Reach-based routing: a new approach to shortest path algorithm optimized for road networks. In: Proceedings of 6th Workshop Algorithm Engineering and Experiments (ALENEX’04), SIAM, pp. 100–111 (2004)

12.

Bast, H., Funke, S., Matijevic, S., Sanders, P., Schultes, D.: Intransit to constant time shortest path queries in road networks. In: Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithmics and Combinatorics, pp. 46–59 (2007)

13.

Bast, H., Funke, S., Sanders, P., Schultes, D.: Fast routing in road networks with transit nodes. Science 316, 566 (2007)MathSciNetCrossRefMATH

14.

Schultes, D., Sanders, P.: Dynamic highway-node routing. In: Proceedings of 6th Workshop on Experimental Algorithms (WEA’07), Lecture Notes in Computer Science, vol. 4525, pp. 66–79. Springer, June 2007

15.

Chlamtac, I., Conti, M., Liu, J.: Mobile ad-hoc networking: imperatives and challenges, pp. 13–64. Ad-Hoc Networks I, Elsevier (2003)

Title: Large Graphs: Fast Cost Update and Query Algorithms. Application for Emergency Vehicles
Author: Ion Cozac
Publisher: Springer International Publishing
Book: Advanced Intelligent Computational Technologies and Decision Support Systems
Print ISBN: 978-3-319-00466-2

Electronic ISBN: 978-3-319-00467-9

Copyright Year: 2014
DOI: https://doi.org/10.1007/978-3-319-00467-9_19

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner