Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
From MaRDI portal
Publication:517802
DOI10.1007/s00453-012-9740-5zbMath1360.68905OpenAlexW2145866065MaRDI QIDQ517802
Mohammad R. Salavatipour, M. Reza Khani
Publication date: 27 March 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9740-5
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
An overview of graph covering and partitioning, Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity, Improved approximation algorithms for some min-max and minimum cycle cover problems, Improved Approximation Algorithms for Min-Max and Minimum Vehicle Routing Problems, Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems, Better approximability results for min-max tree/cycle/path cover problems, Graph covering using bounded size subgraphs, Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover, Unnamed Item, Min-max cover of a graph with a small number of parts, New approximation algorithms for the minimum cycle cover problem, Vehicle routing with subtours, New LP relaxations for minimum cycle/path/tree cover problems, Approximation Algorithms for Generalized Bounded Tree Cover, The \(m\)-Steiner traveling salesman problem with online edge blockages, Approximation algorithms for some minimum postmen cover problems, Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency, New approximation algorithms for the rooted budgeted cycle cover problem
Cites Work
- Min-max tree covers of graphs.
- Approximation hardness of min-max tree covers
- Approximating the \(k\)-traveling repairman problem with repair times
- Approximation algorithms for distance constrained vehicle routing problems
- Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time
- On the Distance Constrained Vehicle Routing Problem
- Approximation Algorithms for Min–Max Tree Partition
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Approximations for minimum and min-max vehicle routing problems
