Parameterized complexity of the \(k\)-arc Chinese postman problem

DOI10.1016/j.jcss.2016.07.006zbMath1353.68132OpenAlexW1801151079MaRDI QIDQ340562

Mohammad Hasan, M. Dambrine

Publication date: 14 November 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2016.07.006

zbMATH Keywords

fixed parameter tractablemixed Chinese postman problem

Mathematics Subject Classification ID

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

Related Items

An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times, Postman problems on series-parallel mixed graphs, Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges, Parameterized algorithms and data reduction for the short secluded s‐t‐path problem, Approximation algorithms for some minimum postmen cover problems, The parameterized complexity of the minimum shared edges problem

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
• Treewidth. Computations and approximations
• Parametrized complexity theory.
• Finding small separators in linear time via treewidth reduction
• The Chinese Postman Problem for Mixed Networks
• On the complexity of edge traversing
• Matching, Euler tours and the Chinese postman
• Networks and vehicle routing for municipal waste collection
• Arc Routing Problems, Part I: The Chinese Postman Problem
• Arc Routing
• Digraphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth