Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Preconditioners for Mixed FEM Solution of Stationary and Nonstationary Porous Media Flow Problems Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures

Authors : Guillaume Chapuis, Hristo Djidjev

Published in: Large-Scale Scientific Computing

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We develop an efficient parallel algorithm for answering shortest-path queries in planar graphs and implement it on a multi-node CPU-GPU clusters. The algorithm uses a divide-and-conquer approach for decomposing the input graph into small and roughly equal subgraphs and constructs a distributed data structure containing shortest distances within each of those subgraphs and between their boundary vertices. For a planar graph with n vertices, that data structure needs O(n) storage per processor and allows queries to be answered in \(O(n^{1/4})\) time.

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 Spin-Based CMOS-Compatible Devices
next chapter A Numerical Approach to Price Path Dependent Asian Options
Literature
1.
Chen, D.Z., Xu, J.: Shortest path queries in planar graphs. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC 2000, pp. 469–478. ACM, New York (2000)
2.
3.
Djidjev, H.: Efficient algorithms for shortest path queries in planar digraphs. In: d’Amore, F., Franciosa, P.G., Marchetti-Spaccamela, A. (eds.) Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science, vol. 1197, pp. 151–165. Springer, Heidelberg (1997)CrossRef
4.
Djidjev, H., Chapuis, G.: Shortest-path queries in planar graphs on GPU-accelerated architectures (arXiv). CoRR (2015). http://​arxiv.​org
5.
Djidjev, H., Thulasidasan, S., Chapuis, G., Andonov, R., Lavenier, D.: Efficient multi-GPU computation of all-pairs shortest paths. In: IPDPS, pp. 360–369 (2014)
6.
Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004–1022 (1987)MATHMathSciNetCrossRef
7.
8.
Karypis, G., Kumar, V.: Multilevel k-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput. 48(1), 96–129 (1998)MathSciNetCrossRef
9.
Mozes, S., Sommer, C.: Exact distance oracles for planar graphs. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 209–222 (2012)
Metadata
Title
Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures
Authors
Guillaume Chapuis
Hristo Djidjev
Copyright Year
2015
Book
Large-Scale Scientific Computing

Print ISBN: 978-3-319-26519-3

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

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-26520-9_5

Premium Partner

    Image Credits