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

A Polynomial 1-Approximation Algorithm for the Windy Postman Problem

作　　者：杜林古[1] 

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

出　　处：《山东纺织工学院学报》1992年第1期50-57,共8页

摘　　要：当投递员穿过边的方向不同,费用就不同时,中国投递员问题就成为带风向的投递员问题(WPP)。本文给出了欧拉图上WPP的一个多项式算法,并由此又给出了WPP的一个多项式1—近似算法。When the cost of traversing an edge depends upon the direction of a postman traversing, the Chinese postman problem will become the windy postman problem(WPP). In this paper, we give a polynomial algorithm for the WPP on the Eulerian graphs and then by this algorithm, give a polynomial 1-approximation algorithm for the general WPP.

关 键 词：带风向 投递员 欧拉图 多项式 

分 类 号：O22[理学—运筹学与控制论]