Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs

DOI10.1016/j.ejor.2007.02.014zbMath1138.90345OpenAlexW2153724959MaRDI QIDQ2462149

Johannes Uhlmann, Erhan Kenar, Falk Hüffner, Jiong Guo, Rolf Niedermeier

Publication date: 23 November 2007

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2007.02.014

zbMATH Keywords

NP-completenessparameterized complexity

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (16)

Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability ⋮ Parameterized complexity of multicut in weighted trees ⋮ Restricted vertex multicut on permutation graphs ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ How to Cut a Graph into Many Pieces ⋮ The critical node detection problem in networks: a survey ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ Unnamed Item ⋮ Simple and improved parameterized algorithms for multiterminal cuts ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Constant ratio fixed-parameter approximation of the edge multicut problem ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Quick separation in chordal and split graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Minimal multicut and maximal integer multiflow: a survey
• Parameterized graph separation problems
• Exact algorithms and applications for tree-like Weighted Set Cover
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A partial k-arboretum of graphs with bounded treewidth
• Treewidth. Computations and approximations
• Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem
• Parametrized complexity theory.
• Fixed-parameter tractability and data reduction for multicut in trees
• Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
• Treewidth: Characterizations, Applications, and Computations
• Graph minors. II. Algorithmic aspects of tree-width
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Two-Commodity Flow
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• The Complexity of Multiterminal Cuts
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Multiway cuts in node weighted graphs
• Practical algorithms on partial k-trees with an application to domination-like problems

This page was built for publication: Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs