Approximating the minmax rooted-tree cover in a tree

DOI10.1016/j.ipl.2007.06.012zbMath1184.68646OpenAlexW2082628447MaRDI QIDQ2380018

Hiroshi Nagamochi, Kohei Okada

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.06.012

zbMATH Keywords

combinatorial problemsdesign of algorithmsgraph algorithmsapproximation algorithmstree partitioningtree covers

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (11)

Improved approximation algorithms for some min-max and minimum cycle cover problems ⋮ Improved Approximation Algorithms for Min-Max and Minimum Vehicle Routing Problems ⋮ On optimal coverage of a tree with multiple robots ⋮ Covering directed graphs by in-trees ⋮ Covering Directed Graphs by In-Trees ⋮ Unnamed Item ⋮ Min-max cover of a graph with a small number of parts ⋮ Online graph exploration algorithms for cycles and trees by multiple searchers ⋮ Approximation results for min-max path cover problems in vehicle routing ⋮ Minmax Tree Cover in the Euclidean Space ⋮ Approximation results for a min-max location-routing problem

Cites Work

• Min-max tree covers of graphs.
• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• Complexity of Task Sequencing with Deadlines, Set-Up Times and Changeover Costs
• Algorithms and Computation
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating the minmax rooted-tree cover in a tree