Approximation hardness of min-max tree covers
DOI10.1016/J.ORL.2010.02.004zbMATH Open1187.90240OpenAlexW1976697723MaRDI QIDQ974986FDOQ974986
Publication date: 8 June 2010
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2010.02.004
Recommendations
- Better inapproximability bounds and approximation algorithms for MIN-MAX tree/cycle/path cover problems
- Improved approximation algorithms for the min-max tree cover and bounded tree cover problems
- Better approximability results for min-max tree/cycle/path cover problems
- Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
- Min-max tree covers of graphs.
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
- Min-max tree covers of graphs.
- On the approximability of the traveling salesman problem
- Algorithms and Computation
- Approximations for minimum and min-max vehicle routing problems
- \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
Cited In (19)
- An overview of graph covering and partitioning
- Approximating the minmax rooted-tree cover in a tree
- Vehicle routing with subtours
- The heterogeneous rooted tree cover problem
- Approximation results for min-max path cover problems in vehicle routing
- Approximation algorithms for some min-max postmen cover problems
- Min-max tree covers of graphs.
- Minimum constellation covers: hardness, approximability and polynomial cases
- Approximation results for a min-max location-routing problem
- Better approximability results for min-max tree/cycle/path cover problems
- Covering a graph with a constrained forest (extended abstract)
- The \(m\)-Steiner traveling salesman problem with online edge blockages
- Approximation and polynomial algorithms for the data mule scheduling with handling time and time span constraints
- Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
- Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems
- Title not available (Why is that?)
- Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover
- Min-max cover of a graph with a small number of parts
- Approximation algorithms for the min-max mixed rural postmen cover problem and its variants
This page was built for publication: Approximation hardness of min-max tree covers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974986)
