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 条
  • [31] A NOVEL 3-WAY TAP
    COBBETT, P
    JOURNAL OF NEUROSCIENCE METHODS, 1980, 3 (01) : 101 - 104
  • [32] A DECOMPOSITION FOR 3-WAY ARRAYS
    LEURGANS, SE
    ROSS, RT
    ABEL, RB
    SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1993, 14 (04) : 1064 - 1083
  • [33] A 3-WAY OCCUPATIONAL FILE
    FRANK, RL
    PATTEN, BB
    VOCATIONAL GUIDANCE QUARTERLY, 1960, 8 (03): : 171 - 172
  • [34] UPDATE ON 3-WAY CATALYSIS
    不详
    AUTOMOTIVE ENGINEERING, 1977, 85 (08): : 50 - 57
  • [35] CONTRACTIONS FOR 3-WAY TABLES
    FLORES, RG
    DATA ANALYSIS, LEARNING SYMBOLIC AND NUMERIC KNOWLEDGE, 1989, : 47 - 54
  • [36] 3-WAY CROSSOVER NETWORK
    EGERTON, MW
    ELECTRONICS & WIRELESS WORLD, 1988, 94 (1623): : 63 - 63
  • [37] DECOMPOSABLE 3-WAY LAYOUTS
    BERUBE, J
    STYAN, GPH
    JOURNAL OF STATISTICAL PLANNING AND INFERENCE, 1993, 36 (2-3) : 311 - 322
  • [38] On 3-way combinatorial identities
    A K Agarwal
    Megha Goyal
    Proceedings - Mathematical Sciences, 2018, 128
  • [39] 3-WAY OUTFLOW ANGIOACCESS
    DOSCHER, W
    SURGERY GYNECOLOGY & OBSTETRICS, 1981, 153 (06): : 902 - 903
  • [40] A 3-WAY VACUUM VALVE
    STEIN, FS
    REVIEW OF SCIENTIFIC INSTRUMENTS, 1954, 25 (05): : 515 - 516
12345