기초과학연구원 이산수학그룹
We give an induced counterpart of the Forest Minor theorem: for any t ≥ 2, the $K_{t,t}$-subgraph-free H-induced-minor-free graphs have bounded pathwidth if and only if H belongs to a class F of forests, which we describe as the induced minors of two (very similar) infinite parameterized families. This constitutes a significant step toward classifying …
We consider an arc-capacitated directed graph $D=(V,A)$, where each node $v$ is associated with a rational balance value $b(v)$. Nodes with negative balance values are referred to as sources, while those with positive balance values are called sinks. A feasible $b$-transshipment is a flow $f : A \to \mathbb{R}_{\ge 0}$ that routes the total supply …
A family of sets in $$ is called an $\ell$-Oddtown if the sizes of all sets are not divisible by $\ell$, but the sizes of pairwise intersections are divisible by $\ell$. The problem was completely solved when $\ell$ is a prime via an elegant linear algebraic method, showing that the family has size at most …