Bounding the Mim-Width of Hereditary Graph Classes.

DOI10.4230/LIPICS.IPEC.2020.6OpenAlexW3111832514MaRDI QIDQ6089650FDOQ6089650

Authors: Nick Brettell, Jake Horsfield, Andrea Munaro, Giacomo Paesani, Daniël Paulusma

Publication date: 13 November 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/13309/pdf/LIPIcs-IPEC-2020-6.pdf/

clique-width hereditary graph class width parameter mim-width

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

Graph minors. X: Obstructions to tree-decomposition
Upper bounds to the clique width of graphs
Approximating clique-width and branch-width
Recent developments on graphs of bounded clique-width
Algorithms for Vertex Partitioning Problems on Partial k-Trees
Clique-width for hereditary graph classes
Title not available (Why is that?)
Boolean-width of graphs
Graph classes with structured neighborhoods and algorithmic applications
Algorithmic aspects of clique-transversal and clique-independent sets
On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
Tight bounds on maximal and maximum matchings
Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
On the induced matching problem
Colouring vertices of triangle-free graphs without forests
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.
Title not available (Why is that?)
Title not available (Why is that?)
Counting minimal transversals of $\beta$-acyclic hypergraphs
Clique-width of graphs defined by one-vertex extensions
The behavior of clique-width under graph operations and graph transformations
Title not available (Why is that?)
Clique-width for graph classes closed under complementation
A width parameter useful for chordal and co-comparability graphs
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
Colouring diamond-free graphs
Understanding model counting for $\beta$-acyclic CNF-formulas
Hardness of computing width parameters based on branch decompositions over the vertex set
Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
Bounding clique-width via perfect graphs
Lower bounds on the mim-width of some graph classes
The point-set embeddability problem for plane graphs
Mim-width. I. Induced path problems
Mim-width. III. Graph powers and generalized distance domination problems
Title not available (Why is that?)
Clique-width and well-quasi-ordering of triangle-free graph classes

Cited In (6)

Mim-width. III. Graph powers and generalized distance domination problems
Solving problems on generalized convex graphs via mim-width
Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
List $k$-colouring $P_t$-free graphs: a mim-width perspective
Steiner trees for hereditary graph classes: a treewidth perspective
Bounding the mim‐width of hereditary graph classes

This page was built for publication: Bounding the Mim-Width of Hereditary Graph Classes.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6089650)