Constant-time algorithms for minimum spanning tree and related problems on processor array with reconfigurable bus systems

Tien Tai Pan, Shun Shii Lin

Research output: Contribution to journalArticle

1 Citation (Scopus)

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 × 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(n3) 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(n3) and O(n2) processors, respectively.

Original languageEnglish
Pages (from-to)174-186
Number of pages13
JournalComputer Journal
Volume45
Issue number2
DOIs
Publication statusPublished - 2002 May 2

Fingerprint

Parallel processing systems

ASJC Scopus subject areas

  • Computer Science(all)

Cite this

Constant-time algorithms for minimum spanning tree and related problems on processor array with reconfigurable bus systems. / Pan, Tien Tai; Lin, Shun Shii.

In: Computer Journal, Vol. 45, No. 2, 02.05.2002, p. 174-186.

Research output: Contribution to journalArticle

@article{0140d3bf27b8441bbf9e7bee9e82b85e,
title = "Constant-time algorithms for minimum spanning tree and related problems on processor array with reconfigurable bus systems",
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 × 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(n3) 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(n3) and O(n2) processors, respectively.",
author = "Pan, {Tien Tai} and Lin, {Shun Shii}",
year = "2002",
month = "5",
day = "2",
doi = "10.1093/comjnl/45.2.174",
language = "English",
volume = "45",
pages = "174--186",
journal = "Computer Journal",
issn = "0010-4620",
publisher = "Oxford University Press",
number = "2",

}

TY - JOUR

T1 - Constant-time algorithms for minimum spanning tree and related problems on processor array with reconfigurable bus systems

AU - Pan, Tien Tai

AU - Lin, Shun Shii

PY - 2002/5/2

Y1 - 2002/5/2

N2 - 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(n3) 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(n3) and O(n2) processors, respectively.

AB - 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(n3) 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(n3) and O(n2) processors, respectively.

UR - http://www.scopus.com/inward/record.url?scp=0036240611&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036240611&partnerID=8YFLogxK

U2 - 10.1093/comjnl/45.2.174

DO - 10.1093/comjnl/45.2.174

M3 - Article

AN - SCOPUS:0036240611

VL - 45

SP - 174

EP - 186

JO - Computer Journal

JF - Computer Journal

SN - 0010-4620

IS - 2

ER -