Abstract
Costa et al. (Oper. Res. Lett. 31:21–27, 2003) presented a quadratic O(min (Kn,n 2)) greedy algorithm to solve the integer multicut and multiflow problems in a rooted tree. (n is the number of nodes of the tree, and K is the number of commodities). Their algorithm is a special case of the greedy type algorithm of Kolen (Location problems on trees and in the rectilinear plane. Ph.D. dissertation, 1982) to solve weighted covering and packing problems defined by general totally balanced (greedy) matrices. In this communication we improve the complexity bound in Costa et al. (Oper. Res. Lett. 31:21–27, 2003) and show that in the case of the integer multicut and multiflow problems in a rooted tree the greedy algorithm of Kolen can be implemented in subquadratic O(K+n+min (K,n)log n) time. The improvement is obtained by identifying additional properties of this model which lead to a subquadratic transformation to greedy form and using more sophisticated data structures.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alon N, Schieber B (1989) Optimal preprocessing for answering on-line product queries. Technical Report, Tel Aviv University
Bender MA, Farach-Colton M (2000) The LCA problem revisited. In: Proceedings of the 4-th Latin American theoretical informatics symposium (LATIN), pp 88–94
Berkman O, Vishkin U (1993) Recursive star-tree parallel data structure. SIAM J Comput 22:221–242
Berkman O, Vishkin U (1994) Finding level-ancestors in tree. J Comput Syst Sci 48:214–230
Chazelle B, Rosenberg B (1991) The complexity of computing partial sums off-line. Int J Comput Geom Appl 1:33–45
Conforti M, Galluccio A, Proietti G (2004) Edge-Connectivity Augmentation and Network Matrices. In: Hrmokovic J, Nagi M, Westfechtel B (eds) Graph-theoretic concepts in computer science, 30-th international workshop 2004, Germany. LNCS, vol 3353. Springer, Berlin, pp 355–364
Costa M-C, Letocart L, Roupin F (2003) A greedy algorithm for multicut and integral multiflow in rooted trees. Oper Res Lett 31:21–27. See Erratum, Oper Res Lett 34:477 (2006)
Frank A (1977) On a class of balanced hypergraphs. Discrete Math 20:11–20
Galluccio A, Proietti G (2003) Polynomial time algorithms for 2-edge connectivity augmentation problems. Algorithmica 36:361–374
Garg N, Vazirani VV, Yannakakis M (1997) Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18:3–20
Harel D (1980) A linear time algorithm for the lowest common ancestors problems. In: Proceedings of the 21-st IEEE symposium on foundations of computer science (FOCS), pp 308–319
Harel D, Tarjan RE (1984) Fast algorithms for finding nearest common ancestors. SIAM J Comput 13:338–355
Hassin R, Tamir A (1991) Improved complexity bounds for location problems on the real line. Oper Res Lett 10:395–402
Hochbaum DS, Levin A (2006) Optimizing over consecutive 1’s and circular 1’s constraints. SIAM J Optim 17:311–330
Hoffman AJ, Kolen A, Sakarovitch M (1985) Totally-balanced and greedy matrices. SIAM J Algebraic Discrete Methods 6:721–730
Kolen A (1982) Location problems on trees and in the rectilinear plane. PhD dissertation, Mathematisch Centrum, Amsterdam
Kolen A (1986) Tree network and planar rectilinear location theory. CWI tract 25, Mathematisch Centrum, Amsterdam
Kolen A, Tamir A (1990) Covering problems. In: Mirchandani PB, Francis RL (eds) Discrete location theory. Wiley, New York
Lubiw A (1987) Doubly lexical ordering of matrices. SIAM J Comput 16:854–879
Paige R, Tarjan RE (1987) Three partition refinement algorithms. SIAM J Comput 16:973–989
Sleator D, Tarjan RE (1983) A data structure for dynamic trees. J Comput Syst Sci 26:362–391
Sleator D, Tarjan RE (1985) Self-adjusting binary trees. J ACM 32:652–685
Spinard JP (1993) Doubly lexical ordering of dense 0–1 matrices. Inf Process Lett 45:229–235
Sharir M, Agarwal PK (1995) Davenport–Schinzel sequences and their geometric applications. Cambridge University Press, Cambridge
Tamir A (1987) Totally balanced and totally unimodular matrices defined by center location problems. Discrete Appl Math 16:245–263
Tarjan RE (1978) Complexity of monotone networks for computing conjunctions. Ann Discrete Math 2:121–133
Tarjan RE (1997) Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math Program 78:167–177
Zhang JZ, Yang XG, Cai MC (2004) Inapproximability and a polynomially solvable special case of a network improvement problem. Eur J Oper Res 155:251–257
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tamir, A. Improved algorithms for the multicut and multiflow problems in rooted trees. TOP 16, 114–125 (2008). https://doi.org/10.1007/s11750-007-0037-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-007-0037-9