Institutional Repository
| unbalanced graph partitioning | |
| Li Angsheng; Zhang Peng | |
| 2010 | |
| Conference Name | 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 |
| Source | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Pages | 218-229 |
| Conference Date | 40878 |
| Conference Place | Jeju Island, Korea, Republic of |
| Indexed Type | EI |
| Publish Place | Germany |
| ISSN | 3029743 |
| ISBN | 3642175163 |
| Department | (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 |
| English Abstract | 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. |
| Keyword | Computational Complexity Trees (Mathematics) |
| Sponsorship | Spec. Interest Group Theor. Comput. Sc. (SIGTCS); Korean Inst. Inf. Sci. Eng. (KIISE) |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/8958 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | Li Angsheng,Zhang Peng. unbalanced graph partitioning[C]. Germany,2010:218-229. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| unbalanced graph par（221KB） | 开放获取 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment