Deformable Polygon Representation and Near-Mincuts
Deformable Polygon Representation and Near-Mincuts
复制标题
可变形多边形表示和近切
DOI：
10.1007/978-3-540-85221-6_3
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
M. Goemans
中科院分区：
文献类型：
--
作者：
A. Benczúr;M. Goemans
我们推导出对称族集合具有涉及凸多边形及其一些对角线的几何表示的充分必要条件。我们证明，小于图边连通性 6/5 倍的值割允许这种表示，从而扩展了所有最小割的仙人掌表示。
We derive a necessary and sufficient condition for a symmetric family of sets to have a geometric representation involving a convex polygon and some of its diagonals. We show that cuts of value less than 6/5 times the edge-connectivity of a graph admit such a representation, thereby extending the cactus representation of all mincuts.