Structural Parameterizations of the Mixed Chinese Postman Problem
Structural Parameterizations of the Mixed Chinese Postman Problem
复制标题
混合中国邮递员问题的结构参数化
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Magnus Wahlström
中科院分区：
文献类型：
--
作者：
G. Gutin;Mark Jones;Magnus Wahlström
在混合的中国邮政问题（MCPP）中，给定加权的混合图G（G可能具有边缘和弧），我们的目的是找到最小的重量闭合步行，至少至少一次。如Van Bevern等人所证明的那样，可以通过G中的边缘数或G中的ARC数量进行参数的MCPP参数。 （2014年）和Gutin，Jones和Sheng（2014）。在本文中，我们考虑了MCPP的未加权版本。解决van Bevern等人的开放问题。 （2014年），我们表明，通过（无向）g的（无向）w的参数为w [1] -hard。实际上，我们证明，即使是通过G路径进行参数的MCPP也是W [1] -hard。在正面，我们证明了由TreeDepth参数化的MCPP是固定参数可进行的。我们不知道路径 - 路径和TreeDepth之间的任何自然图参数，因此我们的结果提供了MCPP复杂性的二分法。
In the Mixed Chinese Postman Problem (MCPP), given a weighted mixed graph G (G may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges in G or the number of arcs in G is fixed-parameter tractable as proved by van Bevern et al. (2014) and Gutin, Jones and Sheng (2014), respectively. In this paper, we consider the unweighted version of MCPP. Solving an open question of van Bevern et al. (2014), we show that somewhat unexpectedly MCPP parameterized by the (undirected) treewidth of G is W[1]-hard. In fact, we prove that even the MCPP parameterized by the pathwidth of G is W[1]-hard. On the positive side, we show that MCPP parameterized by treedepth is fixed-parameter tractable. We are unaware of any natural graph parameters between pathwidth and treedepth and so our results provide a dichotomy of the complexity of MCPP.
第 2 章：圆弧路由问题的复杂性
DOI：
10.1137/1.9781611973679.ch2
发表时间：
2013
期刊：
影响因子：
--
作者：
R. van Bevern;R. Niedermeier;M. Sorge;und M. Weller
通讯作者：
und M. Weller