Better inapproximability bounds and approximation algorithms for MIN-MAX tree/cycle/path cover problems

DOI10.1007/978-3-319-62389-4_45MaRDI QIDQ2412434zbMATH OpenOpenAlexFDO

Authors Wei Yu, Zhaohui Liu

Publication date 23 October 2017

Full work available at URL https://doi.org/10.1007/978-3-319-62389-4_45

zbMATH Keywords

approximation algorithmapproximation hardnesscycle coverpath covertraveling salesman problemtree cover

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Better approximability results for min-max tree/cycle/path cover problems
• Approximation hardness of min-max tree covers
• 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
• Min-max tree covers of graphs.

Cited in

(6)

• Vertex covering by paths on trees with its applications in machine translation
• Better approximability results for min-max tree/cycle/path cover problems
• Inapproximability and approximability of maximal tree routing and coloring
• 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
• Approximation hardness of min-max tree covers

This page was built for publication: Better inapproximability bounds and approximation algorithms for MIN-MAX tree/cycle/path cover problems

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