风向图上两问题的复杂性  

Du Lingu\ Sun Xiaorui (Qingdao University, Qingdao 266071)

作　　者：杜林古[1] 孙孝瑞[1] 

机构地区：[1]青岛大学

出　　处：《青岛大学学报（自然科学版）》1997年第1期12-19,共8页Journal of Qingdao University(Natural Science Edition)

摘　　要：本文证明了风向图上两问题是ＮＰ－完全的和强ＮＰ－完全的．并进一步指出：即使所给风向图是平面的，它们仍是ＮＰ－完全的及强ＮＰ－完全的．这两个问题是：一是叫２ＷＰＰ，它是由带风向投递员问题限制投递员穿过每条边至多两次而得到的问题；This paper shows that two problems on windy graphs are NP-complete and strongly NP-complete and that they remain NP-complete and strongly NP-complete even if the given windy graphs are planar. The two problems are as follows: One is 2WPP, which is got by restricting the postman to traverse each edge no more than twice in the case of the windy postman problem; the other is the maximum weighted cycle packing problem on windy graphs.

关 键 词：风向图 圈装箱 NP-完全性 邮递员问题 图论 

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