Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
From MaRDI portal
Publication:2462149
DOI10.1016/j.ejor.2007.02.014zbMath1138.90345MaRDI 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
90B10: Deterministic network models in operations research
90C27: Combinatorial optimization
90C39: Dynamic programming
Related Items
Unnamed Item, Quick separation in chordal and split graphs, Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs, 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, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, Restricted vertex multicut on permutation graphs, On the parameterized complexity of finding separators with non-hereditary properties, Simple and improved parameterized algorithms for multiterminal cuts, Constant ratio fixed-parameter approximation of the edge multicut problem, 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, How to Cut a Graph into Many Pieces
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
