TSP的一个多项式近似算法被引量：1

A polynomial approximate algorithm to TSP

下载PDF

导出

摘要给出了TSP的一个多项式近似算法,其运算量为O(n3). A polynomial approximate algorithm to TSP is given,whose total number of computation is O（n3）.

作者刘信生陈海钰

机构地区西北师范大学数学与信息科学学院兰州教育学院信息科学系

出处《西北师范大学学报（自然科学版）》 CAS 北大核心 2009年第3期19-21,共3页 Journal of Northwest Normal University(Natural Science)

基金甘肃省自然科学基金资助项目(3ZS051-A25-025) 甘肃省教育厅科研基金资助项目(0501-03)

关键词 TSP 多项式算法半完美1-因子分解 TSP polynomial algorithm semi-perfect 1-factorization

参考文献4

1刘信生.旅行售货员问题的一个多项式近似算法.西北师范学院学报自然科学版,1986,(4):11-15.
2RASTISLAV Královi,Richard Kálovi.On semi-perfet-factorizations[C]//Structural Information and Communication Complexity[M].Berlin:Springer Verlag,2005:216-230.
3EDMONDS J.Paths,trees and flowers[J].Canadian Journal of Mathematics,1965,17(3):449-467.
4BONDY J A,MURTY U S R.Graph Theory with Applications[M].New York:Macmillan Longdon and Elsevier,1976.

1姚会影,周圆,陈光亭,陈永,张安.{1,2}-赋权图最小最大2-路径覆盖问题的近似算法[J].杭州电子科技大学学报（自然科学版）,2022,42(5):89-92.

西北师范大学学报（自然科学版）

2009年第3期

内容加载中请稍等...