Find minimum number of figures needed , so that no additional figure can be added?

You want to compute the independent domination number of a graph with one node per tromino and an edge for each pair of trominoes that overlap. You can solve the problem via integer linear programming, as shown in my answer here. Optimal values for $n \times 2n$ with $n\in\{1,\dots,10\}$ are $0, 2, 3, 6, 9, \color{red}{12}, 17, 22, 28, 35$.

Tags:

Graph Theory

Packing Problem

Discrete Optimization

Related

Approximation to the monkey typewriter probability Calculate area of polygon inside unit square Proving $\lim_{x \to 1}\frac{x+1}{x-2} + x = -1$ using definition How to make sense of the Green's function of the 4D wave equation? In the ring $\mathbb{Z}_p$, $p$ is prime, $(a+b)^p=a^p+b^p$ proof? Find smallest $n$ fulfilling requirement Polynomial with root $α = \sqrt{2}+\sqrt{5}$ and using it to simplify $α^6$ Let $n ≥ 3$. Find the number of NE lattice paths from $(0, 0)$ to $(n, n)$ that touch the diagonal $y = x$ at least twice Infection in a village Prove that $S = \{ f: [0,1]\rightarrow \mathbb{R} \ \text{continuous} : x\in\mathbb{Q}\implies f(x) \in \mathbb{Q}\}$ is. uncountable Show that the sum of a function series is bounded What's the minimum number of $2$s needed to write a positive integer?

Recent Posts