We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 15 Issue 2
March  2000
Turn off MathJax
Article Contents
Abstract
References
WAN Yingyu, XU Yinlong, GU Xiaodong, CHEN Guoliang. Efficient Minimum Spanning Tree Algorithms on the Reconfigurable Mesh[J]. Journal of Computer Science and Technology, 2000, 15(2): 116-125.
Citation: WAN Yingyu, XU Yinlong, GU Xiaodong, CHEN Guoliang. Efficient Minimum Spanning Tree Algorithms on the Reconfigurable Mesh[J]. Journal of Computer Science and Technology, 2000, 15(2): 116-125.
shu

Efficient Minimum Spanning Tree Algorithms on the Reconfigurable Mesh

  • Department of Computer Science and Technology; University of Science and Technology of China National High Performance Computation Center at Hefei; Hefei 230027; P.R. China;

More Information
  • Published Date: March 09, 2000
    Abstract
  • The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log~2 n). The other runs with time complexity of O(log …
    • FullText(HTML)
    • References (3)
  • [1]
    Kruskal J B. On the shortest subtree of a graph and the travelling salesman problem. In Proc. Amer. Math. Soc., 1956, 7(1): 48-50.
    [2]
    Prim R C. Shortest connection networks and some generalizations. Bell System Tech. J., 1957, 36(6): 1389-1401.
    [3]
    Sollin M. An Algorithm Attributed to Sollin. In Introduction to the Design and Analysis of Algorithms, Goodman S E, Hedetniemi S T (eds.), McGraw-Hill, 1977. ……….
    • Relative Articles
  • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (12) PDF downloads (1395) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return