Fixed-parameter tractability and data reduction for multicut in trees
From MaRDI portal
Publication:3367053
DOI10.1002/net.20081zbMath1081.68070OpenAlexW4243521820MaRDI QIDQ3367053
Publication date: 23 January 2006
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.20081
NP-hard problemsfixed-parameter tractabilityexact algorithmsproblem kerneldata reduction rulesMulticut in Trees
Nonnumerical algorithms (68W05) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Logic programming (68N17)
Related Items (16)
Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ A logical approach to multicut problems ⋮ Exact algorithms and applications for tree-like Weighted Set Cover ⋮ Parameterized complexity of weighted multicut in trees ⋮ Parameterized complexity of multicut in weighted trees ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ Query-competitive algorithms for cheapest set problems under uncertainty ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Multicut Is FPT ⋮ On the generalized multiway cut in trees problem ⋮ Multicut in trees viewed through the eyes of vertex cover ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ The critical node detection problem in networks: a survey ⋮ Two fixed-parameter algorithms for vertex covering by paths on trees ⋮ Constant ratio fixed-parameter approximation of the edge multicut problem ⋮ On problems without polynomial kernels
Cites Work
This page was built for publication: Fixed-parameter tractability and data reduction for multicut in trees
