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 条
  • [41] On 3-way combinatorial identities
    Agarwal, A. K.
    Goyal, Megha
    PROCEEDINGS OF THE INDIAN ACADEMY OF SCIENCES-MATHEMATICAL SCIENCES, 2018, 128 (01):
  • [42] 3-WAY BIB DESIGNS
    HEDAYAT, A
    RAGHAVARAO, D
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 1975, 18 (02) : 207 - 209
  • [43] MOLDOVA - A 3-WAY SPLIT
    GAMOVA, S
    BULLETIN OF THE ATOMIC SCIENTISTS, 1994, 50 (01) : 41 - 43
  • [44] 3-WAY BATTLE IN LIPOSOMES
    BLUESTONE, M
    BIO-TECHNOLOGY, 1992, 10 (07): : 732 - &
  • [45] LOOK AT 3-WAY CATHETER
    WHITAKER, RH
    BRITISH JOURNAL OF UROLOGY, 1975, 47 (01): : 103 - 103
  • [46] CHINAS 3-WAY STRETCH
    KIRK, D
    ELECTRONICS, 1967, 40 (17): : 129 - &
  • [47] CARBURETOR FOR 3-WAY CONVERSION
    不详
    AUTOMOTIVE ENGINEERING, 1977, 85 (06): : 38 - 41
  • [48] Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
    Aissi, Hassene
    Mahjoub, A. Ridha
    McCormick, S. Thomas
    Queyranne, Maurice
    MATHEMATICAL PROGRAMMING, 2015, 154 (1-2) : 3 - 28
  • [49] Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
    Hassene Aissi
    A. Ridha Mahjoub
    S. Thomas McCormick
    Maurice Queyranne
    Mathematical Programming, 2015, 154 : 3 - 28
  • [50] 3-WAY ALLIANCE FOR 3DM
    不详
    CIVIL ENGINEERING, 1995, 65 (08): : 19 - 20
12345