KMS Of Academy of mathematics and systems sciences, CAS
judiciousbisectionofhypergraphs | |
Tang Yu Cong1; Xu Xin1; Wang Guang Hui2 | |
2016-01-01 | |
发表期刊 | actamathematicasinicaenglishseries |
ISSN | 1439-8516 |
卷号 | 32期号:5页码:579 |
摘要 | Judicious bisection of hypergraphs asks for a balanced bipartition of the vertex set that optimizes several quantities simultaneously. In this paper, we prove that if G is a hypergraph with n vertices and m(i) edges of size i for i = 1, 2,..., k, then G admits a bisection in which each vertex class spans at most m1/2 + 1/4m(2) + ... + (1/2(k))m(k) + o(m(1) + ... + m(k)) edges, where G is dense enough or Delta(G) = o(n) but has no isolated vertex, which turns out to be a bisection version of a conjecture proposed by Bollobas and Scott. |
语种 | 英语 |
文献类型 | 期刊论文 |
条目标识符 | http://ir.amss.ac.cn/handle/2S8OKBNM/48471 |
专题 | 中国科学院数学与系统科学研究院 |
作者单位 | 1.中国科学院数学与系统科学研究院 2.山东大学 |
推荐引用方式 GB/T 7714 | Tang Yu Cong,Xu Xin,Wang Guang Hui. judiciousbisectionofhypergraphs[J]. actamathematicasinicaenglishseries,2016,32(5):579. |
APA | Tang Yu Cong,Xu Xin,&Wang Guang Hui.(2016).judiciousbisectionofhypergraphs.actamathematicasinicaenglishseries,32(5),579. |
MLA | Tang Yu Cong,et al."judiciousbisectionofhypergraphs".actamathematicasinicaenglishseries 32.5(2016):579. |
条目包含的文件 | 条目无相关文件。 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论