김은정

We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) $(s, t)$-cut of cardinality at most $k$ in an undirected graph $G$ with designated terminals s and t. …