A logical approach to multicut problems

DOI10.1016/J.IPL.2007.03.005MaRDI QIDQ2379958zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

networkscomplexitygraph algorithmsfixed-parameter tractabilityparameterized complexity

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

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

Cites work

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

Cited in

(13)

• scientific article; zbMATH DE number 7278041 (Why is no real title available?)
• scientific article; zbMATH DE number 1538005 (Why is no real title available?)
• Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
• Robust cutpoints in the logical analysis of numerical data
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• scientific article; zbMATH DE number 1757966 (Why is no real title available?)
• 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
• On the parameterized complexity of finding separators with non-hereditary properties
• Multicut Is FPT
• Max-multiflow/min-multicut for G+H series-parallel
• Multicut algorithms via tree decompositions

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)