Mim-width. II. The feedback vertex set problem
From MaRDI portal
Publication:2285053
DOI10.1007/S00453-019-00607-3zbMath1442.05158OpenAlexW2963520829WikidataQ127447102 ScholiaQ127447102MaRDI QIDQ2285053
O-joung Kwon, Jan Arne Telle, Lars Jaffke
Publication date: 16 January 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1956/22364
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (19)
Solving problems on generalized convex graphs via mim-width ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Mim-width. I. Induced path problems ⋮ Bounding the mim‐width of hereditary graph classes ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Recognizing Proper Tree-Graphs ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth ⋮ On \(H\)-topological intersection graphs ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Distance Domination in Graphs ⋮ Mim-width. III. Graph powers and generalized distance domination problems ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Graph classes with structured neighborhoods and algorithmic applications
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Feedback vertex set on AT-free graphs
- Improved algorithms for feedback vertex set problems
- 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
- Feedback vertex set on graphs of low clique-width
- Mim-width. I. Induced path problems
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- On polygon numbers of circle graphs and distance hereditary graphs
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Graph Classes: A Survey
- ON DISJOINT CYCLES
- An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Reducibility among Combinatorial Problems
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Parameterized and Exact Computation
- Parameterized Algorithms
- Computing and Combinatorics
- Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs
This page was built for publication: Mim-width. II. The feedback vertex set problem
