IEICE TRANSACTIONS on Information
Generalized Mesh-Connected Computers with Hyperbus Broadcasting for a Computer Network*
Summary :
The mesh-connected computers with hyperbus broadcasting are an extension of the mesh-connected computers with multiple broadcasting. Instead of using local buses, we use global buses to connect processors. Such a strategy efficiently reduces the time complexity of the semigroup problem from O(N) to O(log N). Also, the matrix multiplication and the transitive closure problems are solved in O(log N) and O(log2 N) time, respectively. Then, based on these operations, several interesting problems such as the connected recognition problem, the articulation problem, the dominator problem, the bridge problem, the sorting problem, the minimum spanning tree problem and the bipartite graph recognition problem can be solved in the order of polylogarithmic time.
- Publication
- IEICE TRANSACTIONS on Information Vol.E79-D No.8 pp.1107-1115
- Publication Date
- 1996/08/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Issue on Architectures, Algorithms and Networks for Massively Parallel Computing)
- Category
- Interconnection Networks
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shi-Jinn HORNG, "Generalized Mesh-Connected Computers with Hyperbus Broadcasting for a Computer Network*" in IEICE TRANSACTIONS on Information,
vol. E79-D, no. 8, pp. 1107-1115, August 1996, doi: .
Abstract: The mesh-connected computers with hyperbus broadcasting are an extension of the mesh-connected computers with multiple broadcasting. Instead of using local buses, we use global buses to connect processors. Such a strategy efficiently reduces the time complexity of the semigroup problem from O(N) to O(log N). Also, the matrix multiplication and the transitive closure problems are solved in O(log N) and O(log2 N) time, respectively. Then, based on these operations, several interesting problems such as the connected recognition problem, the articulation problem, the dominator problem, the bridge problem, the sorting problem, the minimum spanning tree problem and the bipartite graph recognition problem can be solved in the order of polylogarithmic time.
URL: https://global.ieice.org/en_transactions/information/10.1587/e79-d_8_1107/_p
Copy
@ARTICLE{e79-d_8_1107,
author={Shi-Jinn HORNG, },
journal={IEICE TRANSACTIONS on Information},
title={Generalized Mesh-Connected Computers with Hyperbus Broadcasting for a Computer Network*},
year={1996},
volume={E79-D},
number={8},
pages={1107-1115},
abstract={The mesh-connected computers with hyperbus broadcasting are an extension of the mesh-connected computers with multiple broadcasting. Instead of using local buses, we use global buses to connect processors. Such a strategy efficiently reduces the time complexity of the semigroup problem from O(N) to O(log N). Also, the matrix multiplication and the transitive closure problems are solved in O(log N) and O(log2 N) time, respectively. Then, based on these operations, several interesting problems such as the connected recognition problem, the articulation problem, the dominator problem, the bridge problem, the sorting problem, the minimum spanning tree problem and the bipartite graph recognition problem can be solved in the order of polylogarithmic time.},
keywords={},
doi={},
ISSN={},
month={August},}
Copy
TY - JOUR
TI - Generalized Mesh-Connected Computers with Hyperbus Broadcasting for a Computer Network*
T2 - IEICE TRANSACTIONS on Information
SP - 1107
EP - 1115
AU - Shi-Jinn HORNG
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E79-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 1996
AB - The mesh-connected computers with hyperbus broadcasting are an extension of the mesh-connected computers with multiple broadcasting. Instead of using local buses, we use global buses to connect processors. Such a strategy efficiently reduces the time complexity of the semigroup problem from O(N) to O(log N). Also, the matrix multiplication and the transitive closure problems are solved in O(log N) and O(log2 N) time, respectively. Then, based on these operations, several interesting problems such as the connected recognition problem, the articulation problem, the dominator problem, the bridge problem, the sorting problem, the minimum spanning tree problem and the bipartite graph recognition problem can be solved in the order of polylogarithmic time.
ER -
English
