기초과학연구원 이산수학그룹
In , Fabianski et. al. developed a simple, yet surprisingly powerful algorithmic framework to develop efficient parameterized graph algorithms. Notably they derive a simple parameterized algorithm for the dominating set problem on a variety of graph classes, including powers of nowhere dense classes and biclique-free classes. These results encompass a wide range of previously known …
Boolean function analysis for the hypercube $\{ 0, 1 \}^n$ is a well-developed field and has many famous results such as the FKN Theorem or Nisan-Szegedy Theorem. One easy example is the classification of Boolean degree $1$ functions: If $f$ is a real, $n$-variate affine function which is Boolean on the $n$-dimensional hypercube (that is, …
The planar separator theorem by Lipton and Tarjan states that any planar graph with $n$ vertices has a balanced separator of size $O(\sqrt{n})$ that can be found in linear time. This landmark result kicked off decades of research on designing linear or nearly linear-time algorithms on planar graphs. In an attempt to generalize Lipton-Tarjan's theorem …