On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs

DOI10.1016/J.TCS.2023.113825OpenAlexW4324387332MaRDI QIDQ2697441FDOQ2697441

Authors: Andrea Munaro, Shizhou Yang 

Publication date: 12 April 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

Recommendations

• Bounding the mim‐width of hereditary graph classes
• Bounding the Mim-Width of Hereditary Graph Classes.
• Mim-width. I. Induced path problems

zbMATH Keywords

hereditary graph classwidth parametermim-widthsim-width\(\mathsf{XP}\) algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Graph minors. X: Obstructions to tree-decomposition
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Approximating clique-width and branch-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The Complexity of Coloring Circular Arcs and Chords
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Clique-width for hereditary graph classes
• Boolean-width of graphs
• Graph classes with structured neighborhoods and algorithmic applications
• Coloring graphs without short cycles and long induced paths
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Title not available (Why is that?)
• Independent packings in structured graphs
• Clique-width of graphs defined by one-vertex extensions
• Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Colouring \((P_r + P_s)\)-free 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
• More applications of the \(d\)-neighbor equivalence: acyclicity and connectivity constraints
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Combinatorial problems on \(H\)-graphs
• Lower bounds on the mim-width of some graph classes
• The point-set embeddability problem for plane graphs
• Maximum matching width: new characterizations and a fast algorithm for dominating set
• Mim-width. I. Induced path problems
• Treewidth versus clique number in graph classes with a forbidden structure
• Mim-width. III. Graph powers and generalized distance domination problems
• Tree-width dichotomy
• Bounding the mim‐width of hereditary graph classes
• Complexity dichotomy for list-5-coloring with a forbidden induced subgraph

Cited In (4)

• Mim-width. III. Graph powers and generalized distance domination problems
• Bounding the Mim-Width of Hereditary Graph Classes.
• On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
• New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth

This page was built for publication: On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs

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