Mim-width is paraNP-complete
From MaRDI portal
Cites work
- A logic-based algorithmic meta-theorem for mim-width
- A width parameter useful for chordal and co-comparability graphs
- Finding induced subgraphs from graphs with small mim-width
- Graph classes with structured neighborhoods and algorithmic applications
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Hardness of computing width parameters based on branch decompositions over the vertex set
- scientific article; zbMATH DE number 7829295 (Why is no real title available?)
- Mim-width. I. Induced path problems
- Mim-width. III. Graph powers and generalized distance domination problems
- New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth
- Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
- On \(d\)-stable locally checkable problems parameterized by mim-width
- On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
- On the clique-width of some perfect graph classes
- On the complexity of k-SAT
- Parametrized complexity theory.
- The induced separation dimension of a graph
- Which problems have strongly exponential complexity?
This page was built for publication: Mim-width is paraNP-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346456)
