Minmax subtree cover problem on cacti

DOI10.1016/J.DAM.2005.10.013zbMATH Open1103.68143OpenAlexW2033963897MaRDI QIDQ2495907FDOQ2495907

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

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

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)

Cites Work

• Title not available (Why is that?)
• 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
• 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
• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• Efficient implementation of a shifting algorithm
• \((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
• Sales‐delivery man problems on treelike networks

Cited In (7)

• Minmax Tree Cover in the Euclidean Space
• Algorithms and Computation
• Title not available (Why is that?)
• 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)