Hamming距离下瓶颈约束最小支撑树反问题

下载PDF

导出

摘要讨论Hamming距离下瓶颈型约束最小支撑树反问题,给定的一个支撑树,修改给定网络边上的费用,使给定的支撑树成为最小支撑树且支撑树中边费用最大值不超过给定的常数,用瓶颈Ham-ming距离来衡量修改的权值,并给出瓶颈Hamming距离下的约束最小支撑树反问题定理的证明.

作者刘洋唐恒永

机构地区沈阳师范大学数学与系统科学学院

出处《牡丹江师范学院学报（自然科学版）》 2009年第1期1-3,共3页 Journal of Mudanjiang Normal University：Natural Sciences Edition

基金国家自然科学基金项目(10471096)

关键词反问题支撑树 HAMMING距离瓶颈

参考文献7

1Ahuja R K, Orlin J B. Inverse optimization [J]. Oper Res 2001, 35(2) : 771-783.
2Heuburger C. Inverse optimization, a survey on problems, methods, and results[J]. Journal of Combinatorial Optimization, 2004, 12(8) :.. 329-361.
3Orlin J B. Inverse optimization and partial inverse optimization[J]. PPT presentation on Optimization Day Columbia University , 2003, 6 (3): 23-27.
4Hochbaum D S. Efficient algorithms for the inverse spanning tree problem[J]. Operations Research 2003, 51(3): 78-97.
5李淑君,唐恒永.约束最小支撑树问题[J].沈阳师范大学学报（自然科学版）,2006,24(1):13-15. 被引量：3
6Ahuja R K, Magnanti T L, Orlin J B. Networ k Flows[M]. Prentice Hall: Englewood Cliffs, 1993.
7Zhang Bin-wu, Zhang Jian-zhong , He Yong. Constrained inverse minimum spanning tree problems under the bottleneck type Hamming distance[J]. J Comb Optim 2006, 34(5) : 467-474.

1殷剑宏吴开亚.图论及其算法[M].合肥:中国科学技术大学出版社,2004.104-108.
2PRIM P, C. Shortest Connection Networks and Some Generations[J]. Bell System Tech, 1957,36:1389-1401.
3KRUSKAI. J B Jr. On the Shortest Spanning Subtree of a Graph and the Salesman Problem[J ]. Pro Amer Math Soc,1956,7 : 48 - 50.
4Bernhard Korte Jens Vygen. Combinatorial Optimization, 2000.27 : 140 - 146.

2009年第1期

内容加载中请稍等...