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

DOI10.1016/J.EJOR.2007.02.014MaRDI QIDQ2462149zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Falk Hüffner, Erhan Kenar, Johannes Uhlmann, 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)

Recommendations

• SOFSEM 2006: Theory and Practice of Computer Science
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• Restricted vertex multicut on permutation graphs
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset

Cites work

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

Cited in

(20)

• The critical node detection problem in networks: a survey
• A branch-and-price-and-cut method for computing an optimal bramble
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• How to Cut a Graph into Many Pieces
• scientific article; zbMATH DE number 1187148 (Why is no real title available?)
• Restricted vertex multicut on permutation graphs
• On the parameterized complexity of finding separators with non-hereditary properties
• scientific article; zbMATH DE number 7559431 (Why is no real title available?)
• Quick separation in chordal and split graphs
• SOFSEM 2006: Theory and Practice of Computer Science
• Constant factor approximation for tracking paths and fault tolerant feedback vertex set
• Constant factor approximation for tracking paths and fault tolerant feedback vertex set
• Parameterized complexity of multicut in weighted trees
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• Domination and cut problems on chordal graphs with bounded leafage
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• Simple and improved parameterized algorithms for multiterminal cuts
• Constant ratio fixed-parameter approximation of the edge multicut problem

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

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