Lower bounds on the mim-width of some graph classes

DOI10.1016/j.dam.2017.04.043zbMath1395.05172arXiv1608.01542OpenAlexW2569520194MaRDI QIDQ2413964

Stefan Mengel

Publication date: 17 September 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

lower boundmim-widthcircle graphsco-comparability graphsstrongly chordal split graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Well-partitioned chordal graphs ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ 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

Cites Work

• Graph classes with structured neighborhoods and algorithmic applications
• A width parameter useful for chordal and co-comparability graphs
• The Hamiltonian circuit problem for circle graphs is NP-complete
• HAMILTONian circuits in chordal bipartite graphs
• On tree width, bramble size, and expansion
• The point-set embeddability problem for plane graphs
• No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth
• Solving #SAT and MAXSAT by Dynamic Programming
• On Compiling CNFs into Structured Deterministic DNNFs
• On Satisfiability Problems with a Linear Structure
• Unnamed Item

This page was built for publication: Lower bounds on the mim-width of some graph classes