| 二部图上的K1,m划分问题 |
| |
| 引用本文： | 张同全,李建平.二部图上的K1,m划分问题[J].云南大学学报(自然科学版),2005,27(4):277-280. |
| |
| 作者姓名： | 张同全 李建平 |
| |
| 作者单位： | 云南大学,数学系,云南,昆明,650091 |
| |
| 基金项目： | 国家自然科学基金资助项目(10271103)，云南省自然科学基金资助项目(2003F0015M). |
| |
| 摘 要： | 考虑了二部图上的|V|-K1,m划分问题.首先利用网络最大流与网络最小费用流算法给出了赋权二部图上该问题的1个多项式算法,然后证明了:不考虑二部图上的权重或w是一固定常数时,该算法的复杂度为O((|V|+|U|)3.最后证明了:赋权二部图上最小最大|V|-K1,m划分问题是NP-难的.
|
| 关 键 词： | V -K1 m最大流算法 最小费用流算法 NP-难的 |
| 文章编号： | 0258-7971(2005)04-0277-03 |
| 修稿时间： | 2004年11月1日 |
Partition problems of bipartite graphs |
| |
| ZHANG Tong-quan,LI Jian-ping.Partition problems of bipartite graphs[J].Journal of Yunnan University(Natural Sciences),2005,27(4):277-280. |
| |
| Authors: | ZHANG Tong-quan LI Jian-ping |
| |
| Institution: | Department of Mathematics, Yunnan University, Kunming 650091, China |
| |
| Abstract: | |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. |
| |
| Keywords: | Maximum-flow algorithm minimum-cost algorithm hard |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《云南大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《云南大学学报(自然科学版)》下载免费的PDF全文 |
