Parameterized Complexity of the k-Arc Chinese Postman Problem

DOI10.1007/978-3-662-44777-2_44MaRDI QIDQ2921440zbMATH OpenOpenAlexFDO

Authors G. Gutin, Mark Jones, Bin Sheng

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.1512

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: 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 well-known result of Marx, O'Sullivan and Razgon (2013) on the treewidth of torso graphs with respect to small separators. We obtain a small cut analog of this result, and use it to construct a tree decomposition which, despite not having bounded width, has other properties allowing us to design a fixed-parameter algorithm.

Recommendations

• Parameterized complexity of the k-arc Chinese postman problem
• Parameterized complexity of \(k\)-Chinese postman problem
• Parameterized directed k-Chinese postman problem and k arc-disjoint cycles problem on Euler digraphs
• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• Structural parameterizations of the mixed Chinese postman problem
• A Note on K-Best Solutions to the Chinese Postman Problem
• Approximation algorithms for solving the heterogeneous Chinese postman problem
• An approximation algorithm for solving the heterogeneous Chinese postman problem
• Approximation algorithms for a mixed postman problem with restrictions on the arcs
• An algorithm for the hierarchical Chinese postman problem

Cited in

(8)

• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• Parameterized directed k-Chinese postman problem and k arc-disjoint cycles problem on Euler digraphs
• Parameterized complexity of the k-arc Chinese postman problem
• Structural parameterizations of the mixed Chinese postman problem
• Parameterized complexity of \(k\)-Chinese postman problem
• Arc Routing Problems, Part I: The Chinese Postman Problem
• Chinese postman problem on edge-colored multigraphs
• Completing partial schedules for open shop with unit processing times and routing

This page was built for publication: Parameterized Complexity of the k-Arc Chinese Postman Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921440)