Approximation algorithms for some minimum postmen cover problems

DOI10.1016/J.DAM.2022.01.005MaRDI QIDQ5918771zbMATH OpenOpenAlexWikidataFDO

Authors Yuying Mao, Wei Yu, Zhaohui Liu, Jiafeng Xiong

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 algorithmChinese postman problempostmen coverrural postman problemtraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithms for some minimum postmen cover problems
• Approximation algorithms for some min-max postmen cover problems
• Approximation algorithms for the min-max mixed rural postmen cover problem and its variants
• Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover
• scientific article; zbMATH DE number 1187150
• Approximation algorithms for partial covering problems
• scientific article; zbMATH DE number 784428
• An approximation algorithm for the total covering problem
• Approximation Algorithms for Min-Max Cycle Cover Problems
• Approximation algorithms for a mixed postman problem with restrictions on the arcs

Cites work

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

Cited in

(10)

• Approximation algorithms for some min-max postmen cover problems
• The restricted Chinese postman problems with penalties
• Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover
• Approximation algorithms for the single robot line coverage problem
• Covering the edges of a graph by circuits
• A 3/2-Approximation Algorithm for the Mixed Postman Problem
• Approximation algorithms for some min-max and minimum stacker crane cover problems
• Approximation algorithms for some min-max and minimum stacker crane cover problems
• Approximation algorithms for some minimum postmen cover problems
• Approximation algorithms for the restricted k-Chinese postman problems with penalties

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

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