Minmax subtree cover problem on cacti

DOI10.1016/j.dam.2005.10.013zbMath1103.68143OpenAlexW2033963897MaRDI QIDQ2495907

Taizo Kawada, Hiroshi Nagamochi

Publication date: 30 June 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.10.013

zbMATH Keywords

treevehicle routingapproximation algorithmNP-hardcactusgraph partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Unnamed Item ⋮ Minmax Tree Cover in the Euclidean Space

Cites Work

• Unnamed Item
• Efficient implementation of a shifting algorithm
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• A faster 2-approximation algorithm for the minmax \(p\)-traveling salesmen problem on a tree
• An approximability result of 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
• Routing and Scheduling on a Shoreline with Release Times
• Sales‐delivery man problems on treelike networks
• Algorithms and Computation
• A new approximation algorithm for the capacitated vehicle routing problem on a tree

This page was built for publication: Minmax subtree cover problem on cacti