05780411

a

05780411 Xiao, Mingyu Fukunaga, Takuro Nagamochi, Hiroshi FPTAS's for some cut problems in weighted trees. Lee, Der-Tsai (ed.) et al., Frontiers in algorithmics. 4th international workshop, FAW 2010, Wuhan, China, August 11--13, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-14552-0/pbk). Lecture Notes in Computer Science 6213, 210-221 (2010). 2010 Berlin: Springer EN Graph Cut FPTAS Tree Tree Knapsack

doi:10.1007/978-3-642-14553-7_21

Summary: Given a tree with nonnegative edge cost and nonnegative vertex weight, and a number $k \geq 0$, we consider the following four cut problems: cutting vertices of weight at most or at least $k$ from the tree by deleting some edges such that the remaining part of the graph is still a tree and the total cost of the edges being deleted is minimized or maximized. The MinMstCut problem (cut vertices of weight at most $k$ and minimize the total cost of the edges being deleted) can be solved in linear time and space and the other three problems are NP-hard. In this paper, we design an $O(\ln /\epsilon )$-time $O(l ^{2}/\epsilon + n)$-space algorithm for MaxMstCut, and $O(\ln (1/\epsilon + \log n))$-time $O(l ^{2}/\epsilon + n)$-space algorithms for MinLstCut and MaxLstCut, where $n$ is the number of vertices in the tree, $l$ the number of leaves, and $\epsilon > 0$ the prescribed error bound.