Computing Minimum Multiway Cuts in Hypergraphs from Hypertree Packings
Computing Minimum Multiway Cuts in Hypergraphs from Hypertree Packings
复制标题
DOI：
10.1007/978-3-642-13036-6_2
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
Takuro Fukunaga
中科院分区：
文献类型：
--
作者：
Takuro Fukunaga
超图割问题是寻找一个超边的最小容量集的问题，该最小容量集的去除将给定的超图划分为多个连通分支。我们提出了一个算法，该算法运行在强多项式时间，如果bothk和超图的秩是常数。我们的算法扩展了Thorup（2008）的算法，用于从生成树的贪婪填充计算图的最小割。
Hypergraphk-cut problem is a problem of finding a minimum capacity set of hyperedges whose removal divides a given hypergraph intokconnected components. We present an algorithm for this problem which runs in strongly polynomial-time if bothkand the rank of the hypergraph are constants. Our algorithm extends the algorithm due to Thorup (2008) for computing minimumk-cuts of graphs from greedy packings of spanning trees.