Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
DOI10.1007/S00453-012-9740-5zbMATH Open1360.68905OpenAlexW2145866065MaRDI QIDQ517802FDOQ517802
Mohammad 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
Recommendations
- Improved approximation algorithms for the min-max tree cover and bounded tree cover problems
- Approximation algorithms for generalized bounded tree cover
- Generalized bounded tree cover of a graph
- Better inapproximability bounds and approximation algorithms for MIN-MAX tree/cycle/path cover problems
- Algorithms and Computation
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Min-max tree covers of graphs.
- Approximating the \(k\)-traveling repairman problem with repair times
- Approximation algorithms for distance constrained vehicle routing problems
- On the Distance Constrained Vehicle Routing Problem
- Approximations for minimum and min-max vehicle routing problems
- Approximation algorithms for min-max path cover problems with service handling time
- Approximation Algorithms for Min–Max Tree Partition
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Approximation hardness of min-max tree covers
Cited In (25)
- An overview of graph covering and partitioning
- How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover
- Algorithms and Computation
- Approximating the minmax rooted-tree cover in a tree
- Vehicle routing with subtours
- Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems
- Algorithms and Computation
- Improved Approximation Algorithms for Min-Max and Minimum Vehicle Routing Problems
- New LP relaxations for minimum cycle/path/tree cover problems
- Better approximability results for min-max tree/cycle/path cover problems
- Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity
- The \(m\)-Steiner traveling salesman problem with online edge blockages
- Approximation Algorithms for Generalized Bounded Tree Cover
- New approximation algorithms for the rooted budgeted cycle cover problem
- Improved approximation algorithms for some min-max and minimum cycle cover problems
- Approximation algorithms for solving the trip-constrained vehicle routing cover problems
- Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
- New approximation algorithms for the minimum cycle cover problem
- Title not available (Why is that?)
- Improved approximation algorithms for minimum power covering problems
- Approximation algorithms for some minimum postmen cover problems
- Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover
- Induced tree covering and the generalized Yutsis property
- Min-max cover of a graph with a small number of parts
- Graph covering using bounded size subgraphs
This page was built for publication: Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517802)
