张同全, 李建平. 二部图上的K1,m划分问题[J]. 云南大学学报(自然科学版), 2005, 27(4): 277-279,284.
引用本文: 张同全, 李建平. 二部图上的K1,m划分问题[J]. 云南大学学报(自然科学版), 2005, 27(4): 277-279,284.
shu
ZHANG Tong-quan, LI Jian-ping. Partition problems of bipartite graphs[J]. Journal of Yunnan University: Natural Sciences Edition, 2005, 27(4): 277-279,284.
Citation: ZHANG Tong-quan, LI Jian-ping. Partition problems of bipartite graphs[J]. Journal of Yunnan University: Natural Sciences Edition, 2005, 27(4): 277-279,284.
shu

二部图上的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.

     

    • HTML全文
    • 参考文献(0)
    • 相关文章
    • 施引文献
  • 资源附件(0)

/

返回文章
返回