A logical approach to multicut problems

DOI10.1016/J.IPL.2007.03.005zbMATH Open1190.90032OpenAlexW2014767497WikidataQ59259639 ScholiaQ59259639MaRDI QIDQ2379958FDOQ2379958

Authors: Georg Gottlob, Stephanie Tien Lee 

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.03.005

Recommendations

• Multicut algorithms via tree decompositions
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Fixed-parameter tractability and data reduction for multicut in trees
• Multicut Is FPT
• Fixed-parameter tractability of multicut parameterized by the size of the cutset

zbMATH Keywords

networkscomplexitygraph algorithmsfixed-parameter tractabilityparameterized complexity

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Cites Work

• Parametrized complexity theory.
• Easy problems for tree-decomposable graphs
• The Complexity of Multiterminal Cuts
• Parameterized graph separation problems
• Graph minors. II. Algorithmic aspects of tree-width
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fixed-parameter tractability and data reduction for multicut in trees
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• SOFSEM 2006: Theory and Practice of Computer Science
• Primal-dual approximation algorithms for integral flow and multicut in trees

Cited In (13)

• Title not available (Why is that?)
• Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
• Robust cutpoints in the logical analysis of numerical data
• Title not available (Why is that?)
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• On the hardness of finding near-optimal multicuts in directed acyclic graphs
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• On structural parameterizations of the edge disjoint paths problem
• Multicut Is FPT
• On the parameterized complexity of finding separators with non-hereditary properties
• Max-multiflow/min-multicut for G+H series-parallel
• Multicut algorithms via tree decompositions
• Title not available (Why is that?)

This page was built for publication: A logical approach to multicut problems

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