New answers tagged

0

Let us build the tripartite graph $G = (S := U\dot\cup V \dot\cup W, E)$, where $U := \{u_1, \dots u_n\}$ and similarly $V := \{v_1, \dots v_n\}$ and $W := \{w_1, \dots w_n\}$. Define $E$ as follows: For $i, j \in [n]$, we add $(u_i, v_j)$ to $E$ for $u_i \in U$ and $v_j \in V$, if and only if $X_{ij} = 1$. Similarly we add $(v_i, w_j)$ to $E$ for $v_i \in V$...


0

Form a grid graph, with one vertex per cell. Add an edge between each pair of adjacent cells that contain a 0. Add one more start vertex, with an edge from it to every cell on the perimeter that contains a 0. Find all cells reachable from the start vertex (using DFS or BFS), and remove them. Then, count the number of remaining cells containing a 0.


Top 50 recent answers are included