## 摘要

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 × 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 × m × 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.

原文 | 英語 |
---|---|

頁（從 - 到） | 174-186 |

頁數 | 13 |

期刊 | Computer Journal |

卷 | 45 |

發行號 | 2 |

DOIs | |

出版狀態 | 已發佈 - 2002 |

## ASJC Scopus subject areas

- 電腦科學(全部)