%0 Journal Article
%T AN O(|V|~3)ALGORITHM FOR FINDING MINIMUM WEIGHT TRIANGLE-FREE PERFECT 2-MATCHINGS<br>求最小权无三角形完美2-匹配的 O(|V|~3)算法
%A NING QI
%A <br>宁齐
%J 系统科学与数学
%D 1988
%I 
%X 设 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]还同时给出了求最
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=6E709DC38FA1D09A4B578DD0906875B5B44D4D294832BB8E&cid=37F46C35E03B4B86&jid=0CD45CC5E994895A7F41A783D4235EC2&aid=4AD14AAF77338AECE050AE4372D7864A&yid=0702FE8EC3581E51&vid=5D311CA918CA9A03&iid=0B39A22176CE99FB&sid=847B14427F4BF76A&eid=3A0155B37D8FF829&journal_id=1000-0577&journal_name=系统科学与数学&referenced_num=0&reference_num=0