A near optimal algorithm for edge separators (preliminary version)
A near optimal algorithm for edge separators (preliminary version)
复制标题
一种近乎最优的边缘分隔符算法（初步版本）
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
S. Yau
中科院分区：
文献类型：
--
作者：
Fan Chung Graham;S. Yau
我们给出了图分隔符的一个刻画。然后，在一个恒定因子内逼近分隔符的问题可以归结为一个凸函数的最小化问题。我们讨论了相应的最小化问题的多项式时间算法。
We give a characterization for graph separators. The problem of approximating the separator within a constant factor can then be reduced to a minimization problem of convex functions. We discuss polynomial time algorithms for the corresponding minimization problems.