Parameterized complexity of the k-arc Chinese postman problem

DOI10.1016/J.JCSS.2016.07.006zbMATH Open1353.68132OpenAlexW1801151079MaRDI QIDQ340562FDOQ340562

Mark Jones, Bin Sheng, G. Gutin

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

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

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)

Cites Work

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

Cited In (9)

• The parameterized complexity of the minimum shared edges problem
• Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges
• Parameterized Complexity of the k-Arc Chinese Postman Problem
• Arc Routing Problems, Part I: The Chinese Postman Problem
• An updated annotated bibliography on arc routing problems
• Postman problems on series-parallel mixed graphs
• An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
• Approximation algorithms for some minimum postmen cover problems
• Parameterized algorithms and data reduction for the short secluded s‐t‐path problem

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 Q340562)