Solving problems on generalized convex graphs via mim-width

DOI10.1007/978-3-030-83508-8_15OpenAlexW3171819820MaRDI QIDQ832860

Andrea Munaro, Daniël Paulusma, Nick Brettell, Flavia Bonomo-Braberman

Publication date: 25 March 2022

Full work available at URL: https://arxiv.org/abs/2008.09004

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Related Items (6)

Bounding the mim‐width of hereditary graph classes ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ On convexity in split graphs: complexity of Steiner tree and domination ⋮ On the thinness of trees ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ Solving problems on generalized convex graphs via mim-width

Cites Work

• Unnamed Item
• 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
• Boolean-width of graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Recent developments on graphs of bounded clique-width
• Clique-width of graphs defined by one-vertex extensions
• Graph minors. X: Obstructions to tree-decomposition
• 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
• 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
• Graph Classes: A Survey
• More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
• 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
• 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
• Bounding the Mim-Width of Hereditary Graph Classes.

This page was built for publication: Solving problems on generalized convex graphs via mim-width