Solving problems on generalized convex graphs via mim-width
From MaRDI portal
Publication:832860
DOI10.1007/978-3-030-83508-8_15OpenAlexW3171819820MaRDI QIDQ832860FDOQ832860
Authors: Flavia Bonomo, Nick Brettell, Andrea Munaro, Daniël Paulusma 
Publication date: 25 March 2022
Full work available at URL: https://arxiv.org/abs/2008.09004
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Graph Classes: A Survey
- Upper bounds to the clique width of graphs
- Maximum weight induced matching in some subclasses of bipartite graphs
- Approximating clique-width and branch-width
- On the clique-width of some perfect graph classes
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Recent developments on graphs of bounded clique-width
- Independent domination on tree convex bipartite graphs
- Circular convex bipartite graphs: feedback vertex sets
- Feedback Vertex Sets on Tree Convex Bipartite Graphs
- Feedback vertex sets on restricted bipartite graphs
- Clique-width for hereditary graph classes
- Tractable feedback vertex sets in restricted bipartite graphs
- Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs
- Boolean-width of graphs
- Graph classes with structured neighborhoods and algorithmic applications
- Tractable connected domination for restricted bipartite graphs
- Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
- Restricted Bipartite Graphs: Comparison and Hardness Results
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Clique-width of graphs defined by one-vertex extensions
- The stable set problem and the thinness of a graph
- On planar supports for hypergraphs
- Linear MIM-width of trees
- Domination in some subclasses of bipartite graphs
- A width parameter useful for chordal and co-comparability graphs
- On list \(k\)-coloring convex bipartite 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
- On the thinness and proper thinness of a graph
- Understanding model counting for \(\beta\)-acyclic CNF-formulas
- Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth
- More applications of the \(d\)-neighbor equivalence: acyclicity and connectivity constraints
- 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
- Dominating induced matching in some subclasses of bipartite graphs
- Bounding the Mim-Width of Hereditary Graph Classes.
Cited In (9)
- On the thinness of trees
- Mim-width. III. Graph powers and generalized distance domination problems
- M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
- List 3-coloring on comb-convex and caterpillar-convex bipartite graphs
- Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
- Solving problems on generalized convex graphs via mim-width
- Classes of intersection digraphs with good algorithmic properties
- Bounding the mim‐width of hereditary graph classes
- On convexity in split graphs: complexity of Steiner tree and domination
This page was built for publication: Solving problems on generalized convex graphs via mim-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832860)
