| 求最优权对集的一个对偶算法 |
| |
| 引用本文： | 刘桂真. 求最优权对集的一个对偶算法[J]. 数学研究及应用, 1985, 5(4): 101-104 |
| |
| 作者姓名： | 刘桂真 |
| |
| 作者单位： | 山东大学数学研究所 |
| |
| 摘 要： | 1.引言 Edmonds给出了求一个图的最大权对集的算法它是从一个满足原始对偶可行的解出发使其逐步满足互补松驰条件。[1]描述了一个求最大权完美对集原始算法。它是从一个满足互补松驰条件的原始可行解出发,使其逐步满足对偶可行条件。我们给出一个求图的最大权完美对集的对偶算法,它是从一个满足互补松驰条件的对偶可行解出发使其逐步满足可行条件。本算法开始不要求给出图的一个完全对集,其对偶变量的改变法则也较[1]中的法则简单得多。其基本方法仍是用Edmonds的花的算法[2]。我们将说明本文的算法可用来解其他的最优对集问题。本文中采用的术语参看[2]。
|
| 收稿时间： | 1981-09-15 |
| 修稿时间： | 1982-04-06 |
A Dual Algorithm for Optimum Matching |
| |
| Liu Guizhen. A Dual Algorithm for Optimum Matching[J]. Journal of Mathematical Research with Applications, 1985, 5(4): 101-104 |
| |
| Authors: | Liu Guizhen |
| |
| Affiliation: | Institue of Mashematics Shandong University |
| |
| Abstract: | An algorithm for finding a maximum weight perfect matching in a graph is described. It may be used for finding a maximum weight matching and a matching of maximum cardinality with maximum weight in a graph. |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《数学研究及应用》浏览原始摘要信息 |
|
点击此处可从《数学研究及应用》下载全文 |
