HI,欢迎来到学术之家,发表咨询:400-888-7501  订阅咨询:400-888-7502  股权代码  102064
0

树上限制性k-nodemulticut问题的近似算法

作者:杨惠娟; 董延寿; 林仕勋multicut近似算法最大流

摘要:树上的限制性k-node multicut问题(k-CMC(T))是NP难的,针对k-CMC(T)问题本文首先将问题分解成若干个最大流问题设计了近似值为k的算法其中k是参数.其次利用树的性质改进算法降低了算法的时间复杂度得到一个时间度为O(|V|3log2|V|)且近似值不变的算法.算法简单、易懂.

注:因版权方要求,不能公开全文,如需全文,请咨询杂志社

赤峰学院学报·自然科学版

《赤峰学院学报·自然科学版》(CN:15-1343/N)是一本有较高学术价值的大型半月刊,自创刊以来,选题新奇而不失报道广度,服务大众而不失理论高度。颇受业界和广大读者的关注和好评。 《赤峰学院学报·自然科学版》辟有“数理科学与化学”、“工程技术与计算机应用”、“医学与护理”、“体育科学”等栏目。此刊为内蒙古自治区高校优秀学报。

杂志详情