Approximating graphic min-max and minimum cycle/path/tree cover problems

DOI10.1016/J.DAM.2025.05.002MaRDI QIDQ6969935zbMATH OpenFDO

Authors Wei Yu, Zhaohui Liu

Publication date 19 June 2025

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

Full work available at URL https://doi.org/10.1016/J.DAM.2025.05.002

zbMATH Keywords

approximation algorithmcycle covergraphic TSPpath covertree cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Cites work

• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• A Randomized Rounding Approach to the Traveling Salesman Problem
• An overview of graph covering and partitioning
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approximating Graphic TSP by Matchings
• Approximation algorithms for distance constrained vehicle routing problems
• Approximation Algorithms for Min-Max Cycle Cover Problems
• Approximation algorithms for the multi-vehicle scheduling problem
• Approximation hardness of min-max tree covers
• Approximation results for min-max path cover problems in vehicle routing
• Approximations for minimum and min-max vehicle routing problems
• Better approximability results for min-max tree/cycle/path cover problems
• Combinatorial optimization. Theory and algorithms
• Data mule scheduling on a path with handling time and time span constraints
• 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
• Maximum skew-symmetric flows and matchings
• Min-max tree covers of graphs.
• Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs

Cited in

(1)

• Approximation algorithm for the min-max partial tree cover problem

This page was built for publication: Approximating graphic min-max and minimum cycle/path/tree cover problems

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