二部图上的K_(1,m)划分问题  

Partition problems of bipartite graphs

作　　者：张同全[1] 李建平[1] 

机构地区：[1]云南大学数学系,云南昆明650091

出　　处：《云南大学学报（自然科学版）》2005年第4期277-279,284,共4页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学基金资助项目(10271103);云南省自然科学基金资助项目(2003F0015M).

摘　　要：考虑了二部图上的|V|-K1,m划分问题.首先利用网络最大流与网络最小费用流算法给出了赋权二部图上该问题的1个多项式算法,然后证明了:不考虑二部图上的权重或w是一固定常数时,该算法的复杂度为O((|V|+|U|)3.最后证明了:赋权二部图上最小最大|V|-K1,m划分问题是NP-难的.<Abstrcat>|V|-K_(1,m) partition problems of bipartite graphs were considered.A polynomial algorithm was given for this problem by Maximum-flow algorithm and minimum-cost algorithm,and it was proved to be a O((|V|+|U|)~3) algorithm when on unweighted or equal-weight bipartite graphs.The min-max |V|-K_(1,m) partition problems of weighted bipartite graphs was proved to be NP-hard.

关 键 词：|V|—K1.m最大流算法 最小费用流算法 NP-难的 

分 类 号：O157.5[理学—数学]