TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publication References
  4. Accelerating all-pairs shortest path algorithms for bipartite graphs on graphics processing units
 
Options

Accelerating all-pairs shortest path algorithms for bipartite graphs on graphics processing units

Publikationstyp
Journal Article
Date Issued
2022-02-09
Sprache
English
Author(s)
Hanif, Muhammad Kashif  
Zimmermann, Karl-Heinz  
Anees, Asad  
Institut
Eingebettete Systeme E-13  
TORE-URI
http://hdl.handle.net/11420/12205
Journal
Multimedia tools and applications  
Volume
81
Issue
7
Start Page
9549
End Page
9566
Citation
Multimedia Tools and Applications 81 (7): 9549-9566 (2022-03-01)
Publisher DOI
10.1007/s11042-022-12066-0
Scopus ID
2-s2.0-85124519071
Publisher
Springer Science + Business Media B.V
Bipartite graphs are used to model and represent many real-world problems in biological and physical sciences. Finding shortest paths in bipartite graphs is an important task and has numerous applications. Different dynamic programming based solutions to find the shortest paths exists which differ on complexity and structure of graph. The computational complexity of these algorithms is a major concern. This work formulates the parallel versions of Floyd-Warshall and Torgasin-Zimmermann algorithms to compute the shortest paths in bipartite graphs efficiently. These algorithms are mapped to graphics processing unit using tropical matrix product. The performance for different realizations and parameters are compared for Floyd-Warshall and Torgasin-Zimmermann algorithms. Parallel implementation of Torgasin-Zimmermann algorithm attained a speed-up factor of almost 274 when compared with serial Floyd-Warshall algorithm for random-generated undirected graphs.
Subjects
Bipartite graphs
CUDA
Graphics processing unit
Graphs
Parallelization
Shortest path
DDC Class
004: Informatik
510: Mathematik
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback