We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Constant-time Algorithms for Minimum Spanning Tree and Related Problems on Processor Array with Reconfigurable Bus Systems.
- Authors
Tien-Tai Pan; Shun-Shii Lin
- Abstract
A processor array with a reconfigurable bus system is a parallel computation model that consists of a processor array and a reconfigurable bus system. In this paper, a constant-time algorithm is proposed on this model for finding the cycles in an undirected graph. We can use this algorithm to decide whether a specified edge belongs to the minimum spanning tree of the graph or not. This cycle-finding algorithm is designed on a two-dimensional $n\times n$ processor array with a reconfigurable bus system, where $n$ is the number of vertices in the graph. Based on this cycle-finding algorithm, the minimum spanning tree problem and the spanning tree problem can be solved in O(1) time by using fewer processors than before, O($n\times m\times n$) and O($n^3$) processors respectively. This is a substantial improvement over previous known results. Moreover, we also propose two constant-time algorithms for solving the minimum spanning tree verification problem and spanning tree verification problem by using O($n^3$) and O($n^2$) processors, respectively.
- Subjects
ALGORITHMS; PROGRAMMABLE array logic; COMPUTER buses; COMPUTER systems; ELECTRONIC data processing
- Publication
Computer Journal, 2002, Vol 45, Issue 2, p174
- ISSN
0010-4620
- Publication type
Article
- DOI
10.1093/comjnl/45.2.174