Minmax subtree cover problem on cacti

DOI10.1016/J.DAM.2005.10.013MaRDI QIDQ2495907zbMATH OpenOpenAlexFDO

Authors Hiroshi Nagamochi, Taizo Kawada

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

approximation algorithmcactusgraph partitionNP-hardtreevehicle routing

Mathematics Subject Classification ID

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

Recommendations

• Algorithms and Computation
• Approximating the minmax rooted-tree cover in a tree
• Maximal covering tree problems
• Algorithms and Computation
• Minmax tree cover in the Euclidean space
• Minmax Tree Cover in the Euclidean Space
• On the \(k\)-path cover problem for cacti
• Covering a tree with rooted subtrees -- parameterized and approximation algorithms
• Min-max tree covers of graphs.
• A minimum-length covering subtree of a tree

Cites work

• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• A new approximation algorithm for the capacitated vehicle routing problem on a tree
• Algorithms and Computation
• An approximability result of the multi-vehicle scheduling problem on a path with release and handling times
• Efficient implementation of a shifting algorithm
• scientific article; zbMATH DE number 956787 (Why is no real title available?)
• Routing and Scheduling on a Shoreline with Release Times
• Sales‐delivery man problems on treelike networks

Cited in

(7)

• On the \(k\)-path cover problem for cacti
• A minimum-length covering subtree of a tree
• Algorithms and Computation
• Algorithms and Computation
• scientific article; zbMATH DE number 7662164 (Why is no real title available?)
• Minmax Tree Cover in the Euclidean Space
• Maximum max-k-clique subgraphs in cactus subtree graphs

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

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