当前位置: 首页 > 学术报告
Parameterized Complexity of the k-arc Chinese Postman Problem
盛斌 博士(伦敦大学计算机系)
2018-01-01 12:13  华东师范大学

摘要:In the Mixed Chinese Postman Problem (MCPP), given an edge-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 was known to be fixed-parameter tractable using a simple argument. Solving an open question of van Bevern et al., we prove that the MCPP parameterized by the number of arcs is also fixed-parameter tractable. Our proof is more involved and, in particular, uses a very useful result of Marx, O’Sullivan and Razgon (2013) on the treewidth of torso graphs with respect to small separators.