Fixed-parameter tractability and data reduction for multicut in trees

DOI10.1002/NET.20081MaRDI QIDQ3367053zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Rolf Niedermeier

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

zbMATH Keywords

data reduction rulesexact algorithmsfixed-parameter tractabilityMulticut in TreesNP-hard problemsproblem kernel

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Logic programming (68N17) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Communication networks in operations research (90B18)

Recommendations

• Multicut in trees viewed through the eyes of vertex cover
• Algorithms for cut problems on trees
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• Improved parameterized and exact algorithms for cut problems on trees
• Multicut algorithms via tree decompositions

Cites work

• Algorithms and Data Structures
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• On efficient fixed-parameter algorithms for weighted vertex cover

Cited in

(25)

• On problems without polynomial kernels
• The critical node detection problem in networks: a survey
• MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms
• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• 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
• Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
• Algorithms for cut problems on trees
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Multicut algorithms via tree decompositions
• Multicut in trees viewed through the eyes of vertex cover
• Multicut Is FPT
• Multicut in trees viewed through the eyes of vertex cover
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• 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
• 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

This page was built for publication: Fixed-parameter tractability and data reduction for multicut in trees

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