Bounding the mim‐width of hereditary graph classes
From MaRDI portal
Publication:6056798
DOI10.1002/jgt.22730zbMath1522.05394arXiv2004.05018OpenAlexW3195265556MaRDI QIDQ6056798
Jake Horsfield, Daniël Paulusma, Andrea Munaro, Giacomo Paesani, Nick Brettell
Publication date: 4 October 2023
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.05018
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Clique‐width: Harnessing the power of atoms ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ On \(d\)-stable locally checkable problems parameterized by mim-width ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Tree Pivot-Minors and Linear Rank-Width
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
- Solving problems on generalized convex graphs via mim-width
- 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
- 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.
- Edge dominating set and colorings on graphs with fixed clique-width
- 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
- On the tractability of optimization problems on \(H\)-graphs
- List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
- List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
- 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 Complexity of Coloring Circular Arcs and Chords
- 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
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- 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
