mim-width

Relations

Results

• 2012 New Width Parameters of Graphs by Vatshelle
  • page 33 : mim-width – Definition 3.7.1 (MIM-width). For $G$ a graph and $A \subseteq V(G)$ let $mim \colon 2^{V(G)} \to \mathbb N$ be a function where $mim(A)$ is the size of a maximum induced matching in $G[A,\bar A]$. Using Definition 3.1.3 with $f=mim$ we define $mimw(T,\delta$ as the $f$-width of a binary decomposition tree $(T,\delta)$ and $mimw(G)$ as the $f$-width of $G$, also called the MIM-width of $G$ or the maximum induced matching width.
  • page 42 : boolean width upper bounds mim-width by a linear function – Theorem 4.2.10. Let $G$ be a graph, then $mimw(G) \le boolw(G) \le mimw(G) \log_2(n)$
• assumed
  • mim-width is equivalent to mim-width – assumed
• unknown source
  • clique-width upper bounds mim-width by a linear function
  • mim-width upper bounds sim-width by a computable function