| 求最大匹配的一个新算法 |
| |
| 引用本文： | 戴一奇.求最大匹配的一个新算法[J].数学研究及应用,1988,8(4):605-612. |
| |
| 作者姓名： | 戴一奇 |
| |
| 作者单位： | 清华大学 北京 |
| |
| 摘 要： | 简单无向图G的最大匹配问题分为二部图和一般图的最大匹配两类。前者主要采用可增广路的思想解决,〔1〕中已经详述;本文主要讨论有关后者的算法。 定义 设G=(V,E)是简单无向图,在G的所有匹配M′中,若M=max|M′|,则称M是G的一个最大匹配。
|
| 收稿时间： | 7/5/1986 12:00:00 AM |
A New Algorithm for Constructing A Maximum Matching on a Graph |
| |
| Dai Yiqi.A New Algorithm for Constructing A Maximum Matching on a Graph[J].Journal of Mathematical Research with Applications,1988,8(4):605-612. |
| |
| Authors: | Dai Yiqi |
| |
| Institution: | Tsinghua University; Beijing |
| |
| Abstract: | A new algorithm is proposed for constructing a maximum matching in a simple undirected graph.It uses DFS method and proper datastructure to find a alternating tree. In this way, the treatment of blosson and the determination of augme men ting path become very simple. The complexity of the algorithm is O(mn). |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《数学研究及应用》浏览原始摘要信息 |
| 点击此处可从《数学研究及应用》下载免费的PDF全文 |
