题名:  unbalanced graph partitioning 
作者:  Li Angsheng
; Zhang Peng

会议文集:  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

会议名称:  21st Annual International Symposium on Algorithms and Computations, ISAAC 2010

会议日期:  40878

出版日期:  2010

会议地点:  Jeju Island, Korea, Republic of

关键词:  Computational complexity
; Trees (mathematics)

出版地:  Germany

收录类别:  EI

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

主办者:  Spec. Interest Group Theor. Comput. Sc. (SIGTCS); Korean Inst. Inf. Sci. Eng. (KIISE)

英文摘要:  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 ksize) or exactly k (called Eksize), where k is an input parameter. An st cut (A, B) is called unbalanced if its sside is of ksize or Eksize. 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 EkSparsest Cut problem (to find an Eksize cut with the minimum sparsity) is still NPhard. We give a bicriteria approximation algorithm for the kSparsest Cut problem (to find a ksize 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 kConductance problem (to find a ksize cut with the minimum conductance). We also prove that the Min kSize st Cut problem is NPhard and give an O(logn)approximation algorithm for it. © 2010 SpringerVerlag. 
语种:  英语

内容类型:  会议论文

URI标识:  http://ir.iscas.ac.cn/handle/311060/8958

Appears in Collections:  计算机科学国家重点实验室 _会议论文

File Name/ File Size 
Content Type 
Version 
Access 
License 

unbalanced graph partitioning.pdf（221KB）      限制开放    联系获取全文 

Recommended Citation: 
Li Angsheng,Zhang Peng. unbalanced graph partitioning[C]. 见:21st Annual International Symposium on Algorithms and Computations, ISAAC 2010. Jeju Island, Korea, Republic of. 40878.


