论文标题
等级中国邮政邮政问题：丝毫疾病使它变得很困难，但脱节是可以控制的
The Hierarchical Chinese Postman Problem: the slightest disorder makes it hard, yet disconnectedness is manageable
论文作者
论文摘要
层次中国邮政邮局问题是在尊重优先级约束的所有边缘的所有边缘找到最短的遍历。我们表明，即使在链条中分解为链条和无与伦比的类别，与连接类的特殊情况也是NP-HARD。对于线性有序（可能是断开连接的）类的情况，我们通过从农村邮局问题转移结果来获得5/3的拟合和固定参数算法。
The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem.
