On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
From MaRDI portal
Publication:2697441
DOI10.1016/j.tcs.2023.113825OpenAlexW4324387332MaRDI QIDQ2697441
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
Cites Work
- Unnamed Item
- Graph classes with structured neighborhoods and algorithmic applications
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Boolean-width of graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Clique-width of graphs defined by one-vertex extensions
- Graph minors. X: Obstructions to tree-decomposition
- A width parameter useful for chordal and co-comparability graphs
- Combinatorial problems on \(H\)-graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Treewidth versus clique number in graph classes with a forbidden structure
- Tree-width dichotomy
- Mim-width. I. Induced path problems
- 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
- Mim-width. III. Graph powers and generalized distance domination problems
- Lower bounds on the mim-width of some graph classes
- Maximum matching width: new characterizations and a fast algorithm for dominating set
- Coloring graphs without short cycles and long induced paths
- Approximating clique-width and branch-width
- Independent packings in structured graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The point-set embeddability problem for plane graphs
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- The Complexity of Coloring Circular Arcs and Chords
- More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
- Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph
- Clique-width for hereditary graph classes
- Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Bounding the mim‐width of hereditary graph classes
This page was built for publication: On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
