• DocumentCode
    934640
  • Title

    Parallel algorithm for shortest paths

  • Author

    Ghosh, R.K. ; Bhattacharjee, G.P.

  • Author_Institution
    Indian Institute of Technology, Department of Computer Science and Engineering, Kanpur, India
  • Volume
    133
  • Issue
    2
  • fYear
    1986
  • fDate
    3/1/1986 12:00:00 AM
  • Firstpage
    87
  • Lastpage
    93
  • Abstract
    An algorithm for finding a shortest path between each pair of nodes of a positive arc weighted graph on a shared memory model of a single instruction-stream multiple data-stream computer is proposed. The time complexity of the algorithm is of O(log d . log n), where d and n denote the diameter and the number of nodes of the graph, respectively. At most, O(n3) processors are required to achieve this time bound.
  • Keywords
    computational complexity; distributed processing; graph theory; parallel processing; parallel algorithm; positive arc weighted graph; shared memory model; shortest paths; single instruction-stream multiple data-stream computer;
  • fLanguage
    English
  • Journal_Title
    Computers and Digital Techniques, IEE Proceedings E
  • Publisher
    iet
  • ISSN
    0143-7062
  • Type

    jour

  • DOI
    10.1049/ip-e.1986.0009
  • Filename
    4646724
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=934640