The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable
From MaRDI portal
Publication:2661637
DOI10.1016/j.orl.2021.01.017OpenAlexW3128828969MaRDI QIDQ2661637
René van Bevern, Vsevolod A. Afanasev, O. Yu. Tsidulko
Publication date: 7 April 2021
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2011.04022
approximation algorithmrural postman problemNP-hardnessarc routingfixed-parameter algorithmtemporal graphs
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Traveling salesman problems in temporal graphs
- Rural postman parameterized by the number of components of required edges
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Eulerian graphs and related topics. Part 1, Volume 2
- Solving the hierarchical Chinese postman problem as a rural postman problem.
- Which problems have strongly exponential complexity?
- An algorithm for the hierarchical Chinese postman problem
- On the hierarchical Chinese postman problem with linear ordered classes
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
- Postman tour on a graph with precedence relation on arcs
- Scheduling Interval-Ordered Tasks
- On general routing problems
- Matching, Euler tours and the Chinese postman
- Arc Routing Problems, Part II: The Rural Postman Problem
- Reducibility among Combinatorial Problems
- A 1.5-Approximation for Path TSP
This page was built for publication: The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable
