高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种求偶图的所有完备匹配算法

蒋建明 陈立东 张良震

蒋建明, 陈立东, 张良震. 一种求偶图的所有完备匹配算法[J]. 电子与信息学报, 1992, 14(3): 281-285.
引用本文: 蒋建明, 陈立东, 张良震. 一种求偶图的所有完备匹配算法[J]. 电子与信息学报, 1992, 14(3): 281-285.
Jiang Jianming, Chen Lidong, Zhang Liangzhen. AN ALGORITHM FOR FINDING ALL PERFECT MATCHINGS IN A BIPARTITE GRAPH[J]. Journal of Electronics and Information Technology, 1992, 14(3): 281-285.
Citation: Jiang Jianming, Chen Lidong, Zhang Liangzhen. AN ALGORITHM FOR FINDING ALL PERFECT MATCHINGS IN A BIPARTITE GRAPH[J]. Journal of Electronics and Information Technology, 1992, 14(3): 281-285.

一种求偶图的所有完备匹配算法

AN ALGORITHM FOR FINDING ALL PERFECT MATCHINGS IN A BIPARTITE GRAPH

  • 摘要: 求给定偶图的所有完备匹配问题在LSI/VLSI的布图设计方面有着重要的应用。本文提出了一种求解这一问题的算法。(1)提出了许配树的概念并讨论了其性质;(2)证明了任意一棵许配树T(xi)对应于给定偶图的所有完备匹配的定理;(3)给出了求给定偶图的所有完备匹配的算法。本算法已在BST 386 CAD工作站上用C语言实现。运行结果证明了算法的正确性。算法已作为正在研充的VLSI积木块布图设计系统中的一个模块。
  • J. Edmonds, Can. J. Math., 17(1965)3, 449-467.[2]i陈立东,张良震,庄文君,电子学报,16(1988)l,53-58.[3]M.N.S. Swamy et al.,Graphs, Networks, and Algorithms, John Wiley Sons, Inc. New York,(1981).[4]N. Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Inc., (1974), pp. 117-181.[5]M. Fukui et al., IEEE Trans. on CAD, CAD-6(1987)3, 383-391.
  • 加载中
计量
  • 文章访问数:  1949
  • HTML全文浏览量:  53
  • PDF下载量:  438
  • 被引次数: 0
出版历程
  • 收稿日期:  1990-05-07
  • 修回日期:  1991-10-30
  • 刊出日期:  1992-05-19

目录

    /

    返回文章
    返回

    官方微信,欢迎关注