Institutional Repository
| 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. |
| 条目包含的文件 | ||||||
| 文件名称/大小 | 文献类型 | 版本类型 | 开放类型 | 使用许可 | ||
| unbalanced graph par(221KB) | 开放获取 | -- | 请求全文 | |||
| 个性服务 |
| 推荐该条目 |
| 保存到收藏夹 |
| 查看访问统计 |
| 导出为Endnote文件 |
| 谷歌学术 |
| 谷歌学术中相似的文章 |
| [Li Angsheng]的文章 |
| [Zhang Peng]的文章 |
| 百度学术 |
| 百度学术中相似的文章 |
| [Li Angsheng]的文章 |
| [Zhang Peng]的文章 |
| 必应学术 |
| 必应学术中相似的文章 |
| [Li Angsheng]的文章 |
| [Zhang Peng]的文章 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论