Lower bounds on the mim-width of some graph classes

DOI10.1016/j.dam.2017.04.043zbMath1395.05172arXiv1608.01542MaRDI 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 bound; mim-width; circle graphs; co-comparability graphs; strongly chordal split graphs

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

Cites Work

• Unnamed Item
• 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