Approximation algorithms for some minimum postmen cover problems

DOI10.1016/J.DAM.2022.01.005zbMath1496.90079OpenAlexW4226003954WikidataQ114191469 ScholiaQ114191469MaRDI QIDQ5918771

Zhaohui Liu, Jiafeng Xiong, Yuying Mao, Wei Yu

Publication date: 4 August 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2022.01.005

zbMATH Keywords

approximation algorithmtraveling salesman problemrural postman problemChinese postman problempostmen cover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (1)

Approximation algorithms for some min-max and minimum stacker crane cover problems

Cites Work

• Unnamed Item
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• Parameterized complexity of the \(k\)-arc Chinese postman problem
• Improved approximation algorithms for some min-max and minimum cycle cover problems
• Parameterized complexity of \(k\)-Chinese postman problem
• Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
• Min-max tree covers of graphs.
• Heuristics for the rural postman problem
• On the complexity of partitioning graphs into connected subgraphs
• \(k\)-path partitions in trees
• The periodic rural postman problem with irregular services on mixed graphs
• Data mule scheduling on a path with handling time and time span constraints
• Approximation algorithms for some min-max postmen cover problems
• An improved approximation algorithm for the minimum 3-path partition problem
• The path partition problem and related problems in bipartite graphs
• The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable
• Approximation algorithms for distance constrained vehicle routing problems
• Approximation results for min-max path cover problems in vehicle routing
• Arc Routing Problems, Part II: The Rural Postman Problem
• Approximations for minimum and min-max vehicle routing problems
• Combinatorial optimization. Theory and algorithms
• New approximation algorithms for the minimum cycle cover problem
• Approximation algorithms for some minimum postmen cover problems

This page was built for publication: Approximation algorithms for some minimum postmen cover problems