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 条
  • [1] Finding minimum 3-way cuts in hypergraphs
    Xiao, Mingyu
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 2008, 4978 : 270 - 281
  • [2] Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts
    Liang Zhao
    Hiroshi Nagamochi
    Toshihide Ibaraki
    Journal of Combinatorial Optimization, 2001, 5 : 397 - 410
  • [3] Approximating the minimum k-way cut in a graph via minimum 3-way cuts
    Zhao, L
    Nagamochi, H
    Ibaraki, T
    ALGORITHMS AND COMPUTATIONS, 2000, 1741 : 373 - 382
  • [4] Approximating the minimum k-way cut in a graph via minimum 3-way cuts
    Zhao, L
    Nagamochi, H
    Ibaraki, T
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2001, 5 (04) : 397 - 410
  • [5] A fast algorithm for computing minimum 3-way and 4-way cuts
    Nagamochi, H
    Ibaraki, T
    MATHEMATICAL PROGRAMMING, 2000, 88 (03) : 507 - 520
  • [6] A fast algorithm for computing minimum 3-way and 4-way cuts
    Nagamochi, H
    Ibaraki, T
    INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, 1999, 1610 : 377 - 390
  • [7] A fast algorithm for computing minimum 3-way and 4-way cuts
    Hiroshi Nagamochi
    Toshihide Ibaraki
    Mathematical Programming, 2000, 88 : 507 - 520
  • [8] MINIMUM CUTS AND SPARSIFICATION IN HYPERGRAPHS
    Chekuri, Chandra
    Xu, Chao
    SIAM JOURNAL ON COMPUTING, 2018, 47 (06) : 2118 - 2156
  • [9] Computing minimum cuts in hypergraphs
    Chekuri, Chandra
    Xu, Chao
    PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2017, : 1085 - 1100
  • [10] Computing minimum multiway cuts in hypergraphs
    Fukunaga, Takuro
    DISCRETE OPTIMIZATION, 2013, 10 (04) : 371 - 382
12345