期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

最小生成树问题在RMESH上的常数时间算法

A Constant Time Algorithm for MST on RMESH
下载PDF
导出
摘要 提出了在n2×mn2的RMESH模型上常数时间的最小生成树算法,并根据PRAM模拟RMESH的结论,得到了在PRAM上O(logn)时间的最小生成树算法。这2个并行算法的时间复杂度都是当前最好的。 A constant time algorithm for minimum spanning tree problem on a n^2×mn^2 RMESH is introduced. Based on the conclusion of simulating RMESH by PRAM, there is an O （logn） algorithm for MST on PRAM. The time complexity of these algorithms is the best so far.
作者 陈鹏 霍金健 张立昂
机构地区 北京大学信息科学技术学院
出处 《北京大学学报（自然科学版）》 EI CAS CSCD 北大核心 2006年第1期83-88,共6页 Acta Scientiarum Naturalium Universitatis Pekinensis
关键词 RMESH 并行算法 最小生成树 RMESH parallel algorithm minimum spanning tree
分类号 TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献8

  • 1Kruskal J B. On the Shortest Subtree of a Graph and the Traveling Salesman Problem. Proc Amer Math Soc, 1956,7 ( 1 ) : 48-50.
  • 2Prim R C. Shortest Connection Networks and Some Generalizations, Bell System Tech J, 1957, 36 (6) : 1389-1401.
  • 3陈鹏,张立昂.PRAM模型模拟RMESH模型的2种方案[J].北京大学学报（自然科学版）,2005,41(3):465-475. 被引量：1
  • 4Tsin Y H, Chin F Y. Efficient Parallel Algorithms for a Class of Graph Theoretic Problems, SIAM J Comput, 1984,13(3) :580-590.
  • 5Kwan S C, Ruzzo W L. Adaptive Parallel Algorithms for Finding Minimum Spanning Trees. Proc Intern Conf on Parallel Computing, 1984, 439-443.
  • 6Nath D, Maheshwari S N. Parallel Algorithms for the Connected Components and Minimal Tree Problems. Inform Proc Lett, 1982, 14(1):7-11.
  • 7Miller R, Prasanna-Kumar V K, Reisis D, et al. Meshes with Reconfigurable Buses, MIT Conference on Advanced Research in VLSI, 1988, 163-178.
  • 8Wan Y Y, Xu Y L, Gu X D, et al. Efficient Minimum Spanning Tree Algorithms for the Reconfigurable Meshes.Journal of Computer Science and Technology, 2000, 15 (2) :116-125.

二级参考文献9

  • 1Miller R, Prasanna-Kumar V K, Reisis D, et al. Meshes with Reconfigurable Buses. MIT Conference on Advanced Research in VLSI, Cambridge:MIT Press, 1988. 163-178.
  • 2Czumaj A, Stamann V. Simulating Shared Memory in Real Time: on the Computing Power of Reconfigurable Architectures. Information and Computation,1997,137(2):103-120.
  • 3Matias Y, Schuster A. Fast, Efficient Mutual and Self Simulations for Shared Memory and Reconfigurable Meshes. In: Proceedings of 7th IEEE Symposium on Parallel and Distributed Processing. San Antonio,Texas:1995, 238-246.
  • 4Forture S, Wyllie J. Parallelism in Random Access Machine. In: Proceedings of 10^th Annual ACM Symposium On the Theory of Computing, San Diego:1978,114-118.
  • 5Eckstein D M. Simultaneous Memory Access. Tech Rep:TR-79-6, Department of Computer Science, Iowa State University, Iowa City, 1979.
  • 6Kucera L. Parallel Computation and Conflicts in Memory Access. Information. Processing Letters, 1982, 14(2):93-96.
  • 7Vishkin U. Implementation of Simultaneous Memory Address Access in Models that Forbit It. Journal of Algorithms,1983, 4(1):45-50.
  • 8Fich F E, Ragde P,Wegderson A. Simulations among Concurrent-Write PRAMs. Algorithmica, 1988, 3(1):43-51.
  • 9Chlebus B S, Dike K, Hagerup T, et al. Efficient Simulations between Concurrent-Read Concurrent-Write PRAM Models. In: Proc of 13th Symposium on Mathematical Foundations of Computer Science. Carlsbad, Czechoslovakia: 1988,231-239.
北京大学学报（自然科学版）
2006年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部