Mim-width. II. The feedback vertex set problem
From MaRDI portal
Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)
Recommendations
Cites work
- A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
- An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Computing and Combinatorics
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Feedback vertex set on AT-free graphs
- Feedback vertex set on graphs of low clique-width
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fundamentals of parameterized complexity
- Generalized distance domination problems and their complexity on graphs of bounded mim-width
- Graph classes with structured neighborhoods and algorithmic applications
- Graph Classes: A Survey
- scientific article; zbMATH DE number 6118220 (Why is no real title available?)
- scientific article; zbMATH DE number 723367 (Why is no real title available?)
- scientific article; zbMATH DE number 1979503 (Why is no real title available?)
- Improved algorithms for feedback vertex set problems
- Mim-width. I. Induced path problems
- ON DISJOINT CYCLES
- On polygon numbers of circle graphs and distance hereditary graphs
- On the clique-width of some perfect graph classes
- On the parameterized complexity of multiple-interval graph problems
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- On the tractability of optimization problems on \(H\)-graphs
- Parameterized algorithms
- Parameterized and Exact Computation
- Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
- Reducibility among combinatorial problems
- Subset feedback vertex set on graphs of bounded independent set size
Cited in
(34)- Feedback vertex set on graphs of low clique-width
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- Mim-width. I. Induced path problems
- List k-colouring P_t-free graphs: a mim-width perspective
- Mim-width. III. Graph powers and generalized distance domination problems
- Lower bounds on the mim-width of some graph classes
- On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
- A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
- Distance domination in graphs
- Feedback vertex set on graphs of low cliquewidth
- More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
- Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
- Computing subset transversals in \(H\)-free graphs
- Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
- On \(H\)-topological intersection graphs
- Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
- Bounding the mim‐width of hereditary graph classes
- MIP formulations for induced graph optimization problems: a tutorial
- Bounding the Mim-Width of Hereditary Graph Classes.
- Recognizing Proper Tree-Graphs
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- Solving problems on generalized convex graphs via mim-width
- New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth
- Finding induced subgraphs from graphs with small mim-width
- Fixed-parameter algorithms for cardinality-constrained graph partitioning problems on sparse graphs
- XNLP-completeness for parameterized problems on graphs with a linear structure
- On the hardness of generalized domination problems parameterized by mim-width
- Comparing width parameters on graph classes
- XNLP-completeness for parameterized problems on graphs with a linear structure
- Hamiltonicity parameterized by mim-width is (indeed) para-NP-hard
- Non-crossing H-graphs: a generalization of proper interval graphs admitting FPT algorithms
- Hamiltonicity parameterized by mim-width Is (indeed) para-NP-hard
- Solving problems on generalized convex graphs via mim-width
This page was built for publication: Mim-width. II. The feedback vertex set problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2285053)
