Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
From MaRDI portal
Publication:5970812
DOI10.1007/s00453-022-00936-wOpenAlexW2977258053MaRDI QIDQ5970812
Jan Arne Telle, Benjamin Bergougnoux, Charis Papadopoulos
Publication date: 3 May 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1910.00887
Related Items
Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Classifying subset feedback vertex set for \(H\)-free graphs ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph classes with structured neighborhoods and algorithmic applications
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Enumerating minimal subset feedback vertex sets
- Feedback vertex set on AT-free graphs
- Graph minors. X: Obstructions to tree-decomposition
- The complexity of generalized clique covering
- A randomized polynomial kernel for subset feedback vertex set
- Output-polynomial enumeration on graphs of bounded (local) linear MIM-width
- Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
- Mim-width. II. The feedback vertex set problem
- Subset feedback vertex set on graphs of bounded independent set size
- Mim-width. III. Graph powers and generalized distance domination problems
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Faster exact algorithms for some terminal set problems
- An improved parameterized algorithm for the minimum node multiway cut problem
- Subset feedback vertex sets in chordal graphs
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Approximating clique-width and branch-width
- Rank-width and vertex-minors
- On Multiway Cut Parameterized above Lower Bounds
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Treewidth: Characterizations, Applications, and Computations
- The Complexity of Multiterminal Cuts
- An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
- Multiway cuts in node weighted graphs
- More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
- Exact Algorithms via Monotone Local Search
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Graph-Theoretic Concepts in Computer Science
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs
