Abstract
Let G=(V,E) be a connected graph such that edges and vertices are weighted by nonnegative reals. Let p be a positive integer. The minmax subtree cover problem (MSC) asks to find a partition χ = {X 1,X 2,...,X p } of V and a set of p subtrees T 1,T 2,...,T p , each T i containing X i so as to minimize the maximum cost of the subtrees, where the cost of T i is defined to be the sum of the weights of edges in T i and the weights of vertices in X i . In this paper, we propose an O(p 2 n) time (4– 4/(p + 1))-approximation algorithm for the MSC when G is a cactus. This is the first constant factor approximation algorithm for the MSC on a class of non-tree graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asano, T., Katoh, N., Kawashima, K.: A new approximation algorithm for the capacitated vehicle routing problem on a tree. J. Combinatorial Optimization 5, 213–231 (2001)
Averbakh, I., Berman, O.: Sales-delivery man problems on treelike networks. Networks 25, 45–58 (1995)
Averbakh, I., Berman, O.: A heuristic with worst-case analysis for minmax routing of two traveling salesmen on a tree. Discrete Applied Mathematics 68, 17–32 (1996)
Averbakh, I., Berman, O.: (p − 1)/(p + 1)–approximate algorithm for p–traveling salesmen problems on a tree with minmax objective. Discrete Applied Mathematics 75, 201–216 (1997)
Desrosiers, J., Dumas, Y., Solomon, M.M., Soumis, F.: Time constrained routing and scheduling. In: Ball, M.O., Magnanti, T.L. (eds.) Handbooks in Operations Research and Management Science, Network Routing, vol. 8, pp. 35–139. North-Holland, Amsterdam (1995)
Karuno, Y., Nagamochi, H., Ibaraki, T.: Vehicle scheduling on a tree to minimize maximum lateness. Journal of the Operations Research Society of Japan 39, 345–355 (1996)
Karuno, Y., Nagamochi, H., Ibaraki, T.: Vehicle scheduling on a tree with release and handling times. Annals of Operations Research 69, 193–207 (1997)
Nagamochi, H.: Approximating the minmax rooted-subtree cover problem (submitted to a journal)
Nagamochi, H., Okada, K.: A faster 2-approximation algorithm for the minmax p–traveling salesmen problem on a tree. Discrete Applied Mathematics 140, 103–114 (2004)
Nagamochi, H., Okada, K.: Polynomial time 2-approximation algorithms for the minmax subtree cover problem. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 138–147. Springer, Heidelberg (2003)
Perl, Y., Vishkin, U.: Efficient implementation of a shifting algorithm, technique for the partitioning. Discrete Applied Mathematics 12, 71–80 (1985)
Psaraftis, H., Solomon, M., Magnanti, T., Kim, T.: Routing and scheduling on a shoreline with release times. Management Science 36, 212–223 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nagamochi, H., Kawada, T. (2004). Approximating the Minmax Subtree Cover Problem in a Cactus. In: Fleischer, R., Trippen, G. (eds) Algorithms and Computation. ISAAC 2004. Lecture Notes in Computer Science, vol 3341. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30551-4_61
Download citation
DOI: https://doi.org/10.1007/978-3-540-30551-4_61
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24131-7
Online ISBN: 978-3-540-30551-4
eBook Packages: Computer ScienceComputer Science (R0)