A logical approach to multicut problems

DOI10.1016/j.ipl.2007.03.005zbMath1190.90032OpenAlexW2014767497WikidataQ59259639 ScholiaQ59259639MaRDI QIDQ2379958

Stephanie Tien Lee, Georg Gottlob

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

complexitynetworksgraph algorithmsfixed-parameter tractabilityparameterized complexity

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Related Items (10)

Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ On the complexity of rainbow coloring problems ⋮ Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability ⋮ Multicut Is FPT ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ Max-multiflow/min-multicut for G+H series-parallel ⋮ On the hardness of finding near-optimal multicuts in directed acyclic graphs ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Unnamed Item

Cites Work

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

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