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

treegraph partitionapproximation algorithmcactusNP-hardvehicle routing

Mathematics Subject Classification ID

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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

• scientific article; zbMATH DE number 956787 (Why is no real title available?)
• 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
• 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
• Routing and Scheduling on a Shoreline with Release Times
• Sales‐delivery man problems on treelike networks
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective

Cited in

(7)

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

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)