FPTAS’s for Some Cut Problems in Weighted Trees

DOI10.1007/978-3-642-14553-7_21zbMATH Open1288.68280OpenAlexW1499833276MaRDI QIDQ3587352FDOQ3587352

Mingyu Xiao, Hiroshi Nagamochi, Takuro Fukunaga

Publication date: 7 September 2010

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-14553-7_21

Recommendations

• On weighted multiway cuts in trees
• FPTASs for trimming weighted trees
• Parameterized complexity of weighted multicut in trees
• Parameterized complexity of multicut in weighted trees
• An FPT 2-approximation for tree-cut decomposition
• An FPT 2-approximation for tree-cut decomposition
• On the generalized multiway cut in trees problem
• On the generalized multiway cut in trees problem
• Improved parameterized and exact algorithms for cut problems on trees
• Algorithms for cut problems on trees

zbMATH Keywords

FPTASgraph cuttree knapsack

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (1)

• An FPT 2-approximation for tree-cut decomposition

This page was built for publication: FPTAS’s for Some Cut Problems in Weighted Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587352)