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. Publications
  4. An all-pairs shortest path algorithm for bipartite graphs
 
Options

An all-pairs shortest path algorithm for bipartite graphs

Citation Link: https://doi.org/10.15480/882.15551
Publikationstyp
Journal Article
Date Issued
2013-12-01
Sprache
English
Author(s)
Torgasin, Svetlana  
Eingebettete Systeme E-13  
Zimmermann, Karl-Heinz  
TORE-DOI
10.15480/882.15551
TORE-URI
https://hdl.handle.net/11420/56665
Journal
Open computer science  
Volume
3
Issue
4
Start Page
149
End Page
157
Citation
Open computer science 3 (4): 149-157 (2013)
Publisher DOI
10.2478/s13537-013-0110-4
Publisher
Versita
Abstract Bipartite graphs are widely used for modeling of complex structures in biology, engineering, and computer science. The search for shortest paths in such structures is a highly demanded procedure that requires optimization. This paper presents a variant of the all-pairs shortest path algorithm for bipartite graphs. The method is based on the distance matrix product and improves the general algorithm by exploiting the graph topology. The space complexity is reduced by a factor of at least four and the time complexity decreased by almost an order of magnitude when compared with the basic APSP algorithm.
Subjects
bipartite graph
tropical (min-plus) algebra
shortest path
distance matrix product
DDC Class
510: Mathematics
Publication version
publishedVersion
Lizenz
https://creativecommons.org/licenses/by-nc-nd/3.0/
Loading...
Thumbnail Image
Name

10.2478_s13537-013-0110-4.pdf

Type

Main Article

Size

379.31 KB

Format

Adobe PDF

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