Finding minimum 3-way cuts in hypergraphs

被引：15
|
作者：
Xiao, Mingyu [1 ]
机构：
[1] Univ Elect Sci & Technol China, Chengdu 610054, Peoples R China
来源：
INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 14-15期
基金：
中国国家自然科学基金;
关键词：
Graph algorithms; k-way cut; Hypergraph; ALGORITHM;
D O I：
10.1016/j.ipl.2010.05.003
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The minimum 3-way cut problem in an edge-weighted hypergraph is to find a partition of the vertices into 3 nonempty sets minimizing the total weight of hyperedges that have at least two endpoints in two different sets. In this paper we show that a minimum 3-way cut in hypergraphs can be found by using O(n(3)) hypergraph minimum (s, t) cut computations, where n is the number of vertices in the hypergraph. Our simple algorithm is the first polynomial-time algorithm for finding minimum 3-way cuts in hypergraphs. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码：554 / 558
页数：5
相关论文
共 50 条
12345