A 3/2-Approximation Algorithm for the Mixed Postman Problem
A 3/2-Approximation Algorithm for the Mixed Postman Problem
复制标题
混合邮差问题的3/2近似算法
DOI：
10.1137/s0895480197331454
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
J. Veerasamy
中科院分区：
文献类型：
--
作者：
B. Raghavachari;J. Veerasamy
混合的邮递员问题是中国邮局问题的概括，是找到至少一次穿越给定混合图的每个边缘的最短巡回赛（至少包含无向边缘和有向边缘的图）。如果图形是无向的，或者图形是指导的，则可以在多项式时间内解决问题，但在混合图中是NP-HARD。提出了一种在混合图上的邮递员问题的近似算法，其性能比为3/2。
The mixed postman problem, a generalization of the Chinese postman problem, is that of finding the shortest tour that traverses each edge of a given mixed graph (a graph containing both undirected and directed edges) at least once. The problem is solvable in polynomial time either if the graph is undirected or if the graph is directed, but it is NP-hard in mixed graphs. An approximation algorithm with a performance ratio of 3/2 for the postman problem on mixed graphs is presented.