Solving problems on generalized convex graphs via mim-width
From MaRDI portal
Publication:6183361
DOI10.1016/j.jcss.2023.103493OpenAlexW3055239807MaRDI QIDQ6183361
Daniël Paulusma, Nick Brettell, Andrea Munaro, Flavia Bonomo-Braberman
Publication date: 4 January 2024
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2023.103493
Cites Work
- Circular convex bipartite graphs: feedback vertex sets
- Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
- Graph classes with structured neighborhoods and algorithmic applications
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Feedback vertex sets on restricted bipartite graphs
- Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
- Boolean-width of graphs
- Thinness of product graphs
- Solving problems on generalized convex graphs via mim-width
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- An optimal greedy heuristic to color interval graphs
- Recent developments on graphs of bounded clique-width
- Clique-width of graphs defined by one-vertex extensions
- The complexity of colouring problems on dense graphs
- A unified approach to domination problems on interval graphs
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
- Graph minors. X: Obstructions to tree-decomposition
- Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
- Domination in some subclasses of bipartite graphs
- A width parameter useful for chordal and co-comparability graphs
- Upper bounds to the clique width of graphs
- Maximum weight induced matching in some subclasses of bipartite 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
- Linear MIM-width of trees
- Tractable connected domination for restricted bipartite graphs
- On the thinness and proper thinness of a graph
- Approximating clique-width and branch-width
- Hard coloring problems in low degree planar bipartite graphs
- The stable set problem and the thinness of a graph
- Independent Domination on Tree Convex Bipartite Graphs
- Feedback Vertex Sets on Tree Convex Bipartite Graphs
- Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth
- Polynomial-Time Data Reduction for the Subset Interconnection Design Problem
- Graph Classes: A Survey
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- List Partitions
- Precoloring Extension III: Classes of Perfect Graphs
- Clique-width for hereditary graph classes
- Tractable Feedback Vertex Sets in Restricted Bipartite Graphs
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Restricted Bipartite Graphs: Comparison and Hardness Results
- Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs
- Maximum matching in a convex bipartite graph
- On Planar Supports for Hypergraphs
- 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
- On \(H\)-topological intersection graphs
- Bounding the mim‐width of hereditary graph classes
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Solving problems on generalized convex graphs via mim-width
