| unbalanced graph partitioning |
| Li Angsheng; Zhang Peng
|
| 2010
|
| 会议名称 | 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
|
| 会议录名称 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|
| 页码 | 218-229
|
| 会议日期 | 40878
|
| 会议地点 | Jeju Island, Korea, Republic of
|
| 收录类别 | EI
|
| 出版地 | Germany
|
| ISSN | 3029743
|
| ISBN | 3642175163
|
| 部门归属 | (1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China; (2) School of Computer Science and Technology, Shandong University, Jinan 250101, China
|
| 摘要 | We investigate the unbalanced cut problems. A cut (A, B) is called unbalanced if the size of its smaller side is at most k (called k-size) or exactly k (called Ek-size), where k is an input parameter. An s-t cut (A, B) is called unbalanced if its s-side is of k-size or Ek-size. We consider three types of unbalanced cut problems, in which the quality of a cut is measured with respect to the capacity, the sparsity, and the conductance, respectively. We show that even if the input graph is restricted to be a tree, the Ek-Sparsest Cut problem (to find an Ek-size cut with the minimum sparsity) is still NP-hard. We give a bicriteria approximation algorithm for the k-Sparsest Cut problem (to find a k-size cut with the minimum sparsity), which outputs a cut whose sparsity is at most O(logn) times the optimum and whose smaller side has size at most O(logn)k. As a consequence, this leads to a (O(logn), O(logn))- approximation algorithm for the Min k-Conductance problem (to find a k-size cut with the minimum conductance). We also prove that the Min k-Size s-t Cut problem is NP-hard and give an O(logn)-approximation algorithm for it. © 2010 Springer-Verlag. |
| 关键词 | Computational Complexity
Trees (Mathematics)
|
| 主办者 | Spec. Interest Group Theor. Comput. Sc. (SIGTCS); Korean Inst. Inf. Sci. Eng. (KIISE)
|
| 语种 | 英语
|
| 内容类型 | 会议论文
|
| URI标识 | http://ir.iscas.ac.cn/handle/311060/8958
|
| 专题 | 基础软件与系统重点实验室
|
推荐引用方式
GB/T 7714 |
Li Angsheng,Zhang Peng. unbalanced graph partitioning[C]. Germany,2010:218-229.
|
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论