Bounding the Mim-Width of Hereditary Graph Classes.
From MaRDI portal
Publication:6089650
DOI10.4230/lipics.ipec.2020.6OpenAlexW3111832514MaRDI QIDQ6089650
Nick Brettell, Giacomo Paesani, Jake Horsfield, Daniël Paulusma, Andrea Munaro
Publication date: 13 November 2023
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/13309/pdf/LIPIcs-IPEC-2020-6.pdf/
Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Solving problems on generalized convex graphs via mim-width ⋮ Steiner trees for hereditary graph classes: a treewidth perspective ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
Cites Work
- Unnamed Item
- 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
- The behavior of clique-width under graph operations and graph transformations
- On the induced matching problem
- Boolean-width of graphs
- Colouring vertices of triangle-free graphs without forests
- Recent developments on graphs of bounded clique-width
- Clique-width of graphs defined by one-vertex extensions
- Graph minors. X: Obstructions to tree-decomposition
- A width parameter useful for chordal and co-comparability graphs
- Counting minimal transversals of \(\beta\)-acyclic hypergraphs
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
- Tight bounds on maximal and maximum matchings
- Algorithmic aspects of clique-transversal and clique-independent sets
- Upper bounds to the clique width of graphs
- Mim-width. I. Induced path problems
- List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
- List coloring in the absence of a linear forest
- Mim-width. II. The feedback vertex set problem
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- Mim-width. III. Graph powers and generalized distance domination problems
- Colouring diamond-free graphs
- Lower bounds on the mim-width of some graph classes
- Bounding clique-width via perfect graphs
- Approximating clique-width and branch-width
- The point-set embeddability problem for plane graphs
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Clique-Width for Graph Classes Closed under Complementation
- Clique-width for hereditary graph classes
- GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Clique-width and well-quasi-ordering of triangle-free graph classes
- Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
