带风向投递员问题的又一多项式1——近似算法  

ANOTHER POLYNOMIAL 1-APPROXIMATION ALGORITHM FOR THE WINDY POSTMAN PROBLEM

作　　者：杜林古[1] 

机构地区：[1]山东纺织工学院会计学系

出　　处：《山东纺织工学院学报》1992年第4期70-77,共8页

摘　　要：本文提出了带风向投递员问题(WPP)的一整数线性规划形式,并由此给出了WPP的一个多项式1——近似算法。文中指出:当所给风向图是欧拉图时,由这一近似算法求得的投递员路线是最优的投递员路线。This paper proposes an integer linear programming formulation for the windy postman problem (WPP). By making use of the formulation, we give out another polynomial 1—approximation algorithm for the WPP. It is also shown that the postman route obtained by this approximation algorithm is optimal if the given windy graph is Eulerian.

关 键 词：整数规划 近似算法 图论 

分 类 号：O157.5[理学—数学]