二部图上的K1,m划分问题
Partition problems of bipartite graphs
-
摘要: 考虑了二部图上的|V|-K1,m划分问题.首先利用网络最大流与网络最小费用流算法给出了赋权二部图上该问题的1个多项式算法,然后证明了:不考虑二部图上的权重或w是一固定常数时,该算法的复杂度为O((|V|+|U|)3.最后证明了:赋权二部图上最小最大|V|-K1,m划分问题是NP-难的.Abstract: |V|-K1,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|-K1,m partition problems of weighted bipartite graphs was proved to be NP-hard.
下载: