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

DOI10.1016/J.TCS.2023.113825MaRDI QIDQ2697441zbMATH OpenOpenAlexFDO

Authors Andrea Munaro, Shizhou Yang

Publication date 12 April 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

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

Cites work

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

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)