A Shortest Path Algorithm for Banded Matrices by a Mesh Connection without Processor Penalty

スポンサーリンク

概要

• 論文の詳細を見る

• We give an efficient shortest path algorithm on a mesh-connected processor array for n × n banded matrices with bandwidth b. We use a ⌈ b/2 ⌉ × ⌈ b/2 ⌉ semisystolic processor array. The input data is supplied to the processor array from the host computer. The output from the processor array can be also supplied to itself through the host computer. This algorithm computes all pair shortest distances within the band in 7n-4 ⌈ b/2 ⌉ -1 steps.

• 社団法人電子情報通信学会の論文
• 1995-03-25

著者

• Mei Aohan

  Faculty Of Engineering Gunma University

• Igarashi Yoshihide

  Faculty Of Engineering Gunma University

関連論文

• Broadcasting in Hypercubes with Randomly Distributed Byzantine Faults
• Reliability of Hypercubes for Broadcasting with Random Faults
• Some Results on Decomposability of Weakly Invertible Finite Automata
• A Shortest Path Algorithm for Banded Matrices by a Mesh Connection without Processor Penalty
• Navigating in Unknown Environment with Rectangular Obstacles
• Some Modifications of the Tournament Algorithm for the Mutual Exclusion Problem
• A Robot Navigation Strategy in Unknown Environment and Its Efficiency (Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク