Solving an All-Pairs Shortest Paths Problem on a Processor Array with Separable Buses

• MAEBA Takashi

  Faculty of Mercantile Marine Science, Kobe University of Mercantile Marine

• SUGAYA Mitsuyoshi

  NRI Secure Technologies

• TATSUMI Shoji

  Faculty of Engineering, Osaka City University

• ABE Ken'ichi

  Faculty of Engineering, Tohoku University

抄録

We propose an algorithm for computing an N-vertices all-pairs shortest paths problem and the related problem on an N×N×√<N/(log fog N)>×√<N/(log fog N)>-processor array with separable buses in O(log log N log N) time. This improves the result on a hyper-bus broadcast network in computational cost asymptotically.

収録刊行物

• IEICE transactions on fundamentals of electronics, communications and computer sciences

  IEICE transactions on fundamentals of electronics, communications and computer sciences 85 (3), 732-, 2002-03-01

  一般社団法人電子情報通信学会

キーワード

• processor array with separable buses
• parallel algorithm
• all-pairs shortest paths
• minimum-weight spanning tree

詳細情報

• CRID: 1571417127441152640
• NII論文ID: 110003216814
• NII書誌ID: AA10826239
• ISSN: 09168508
• 本文言語コード: en
• データソース種別:
  • CiNii Articles