Fixed-parameter tractability and data reduction for multicut in trees
From MaRDI portal
Publication:3367053
DOI10.1002/net.20081zbMath1081.68070MaRDI 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 problems; fixed-parameter tractability; exact algorithms; problem kernel; data reduction rules; Multicut in Trees
68W05: Nonnumerical algorithms
90B18: Communication networks in operations research
68M10: Network design and communication in computer systems
68R10: Graph theory (including graph drawing) in computer science
68N17: Logic programming
Related Items
Multicut Is FPT, Parameterized complexity of weighted multicut in trees, Parameterized complexity of multicut in weighted trees, A survey of parameterized algorithms and the complexity of edge modification, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, Multicut in trees viewed through the eyes of vertex cover, Exact algorithms and applications for tree-like Weighted Set Cover, Improved parameterized and exact algorithms for cut problems on trees, Query-competitive algorithms for cheapest set problems under uncertainty, 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, The critical node detection problem in networks: a survey, A logical approach to multicut problems, On the generalized multiway cut in trees problem, Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
Cites Work
