微信服务号

微信订阅号

2025年6月1日 22:50 星期日
首页 > 过刊浏览>1999年第10卷第1期 >107-110
PDF HTML阅读 XML下载 导出引用 引用提醒
无向图的边极大匹配并行算法及其应用*
作者:
基金项目:

本文研究得到国家自然科学基金、国家863高科技项目基金、山东省自然科学基金和山东大学跨世纪人才基金资助.


A Parallel Maximal Matching Algorithm for Undirected Graphs with Applications
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献
    • |
  • 相似文献
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    在EREW PRAM(exclusive-read and exclusive-write parallel random access machine)并行计算模型上,对范围很广的一类无向图的边极大匹配问题,给出时间复杂性为O(logn),使用O((n+m)/logn)处理器的最佳、高速并行算法.

    Abstract:

    A fast and optimal parallel maximal matching algorithm is proposed for a class of graphs. It runs in O(logn) time with O((n+m)/logn) processors on a EREW PRAM (exclusive-read and exclusive-write parallel random access machine).

    参考文献
    相似文献
    引证文献
引用本文

马 军,岩间一雄,顾谦平.无向图的边极大匹配并行算法及其应用*.软件学报,1999,10(1):107-110

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:1997-03-27
  • 最后修改日期:1998-01-05
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号