| 求最小权无三角形完美2-匹配的 O(|V|~3)算法 |
| |
| 引用本文： | 宁齐.求最小权无三角形完美2-匹配的 O(|V|~3)算法[J].系统科学与数学,1988,8(2):188-189. |
| |
| 作者姓名： | 宁齐 |
| |
| 作者单位： | 山东师范大学计算机系 |
| |
| 摘 要： | 设 G=(V,E)是一简单图.E(G)和 V(G)分别表示 G 的边集合和顶点集合.G 的一个无三角形2-匹配是一个整数向量 x=(x_e:e∈E(G)),使得x_e≥0,(?)_e∈E(G),(1)x(δ(v))≤2,(?)_v∈V(G),(2)x(γ(s))≤2,(?)S(?)V(G),|S|=3.(3)若 x 进一步使(2)都以等式成立,则 x 称为是无三角形完美2-匹配.文献1]证明了:(1)—(3)的可行解集合就是 G 的无三角形2-匹配的凸包多面体.1]还同时给出了求最
|
AN O(|V|~3)ALGORITHM FOR FINDING MINIMUM WEIGHT TRIANGLE-FREE PERFECT 2-MATCHINGS |
| |
| NING QI.AN O(|V|~3)ALGORITHM FOR FINDING MINIMUM WEIGHT TRIANGLE-FREE PERFECT 2-MATCHINGS[J].Journal of Systems Science and Mathematical Sciences,1988,8(2):188-189. |
| |
| Authors: | NING QI |
| |
| Institution: | Department of Computer Science,Shandong Teachers' University |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 |
| 点击此处可从《系统科学与数学》下载免费的PDF全文 |
|
