论文标题
大约最小切割及其枚举
Approximate minimum cuts and their enumeration
论文作者
论文摘要
我们表明，连接图中的每$α$ - 最低限度是某些子集$ s $ $ s $和$ t $ t $ tertices的唯一最小$（s，t）$ - 最多最多$ \lfloor2α\ rfloor+1 $。这导致了另一种证据表明，在$ n $ vertex连接的图中，$α$ appimima的最小削减的数量为$ n^{o（α）} $，并且可以在确定性的多项式时间中列举它们的常数$α$。
We show that every $α$-approximate minimum cut in a connected graph is the unique minimum $(S,T)$-terminal cut for some subsets $S$ and $T$ of vertices each of size at most $\lfloor2α\rfloor+1$. This leads to an alternative proof that the number of $α$-approximate minimum cuts in a $n$-vertex connected graph is $n^{O(α)}$ and they can all be enumerated in deterministic polynomial time for constant $α$.
