关于二分图匈牙利算法的复杂度
  • 板块学术版
  • 楼主World_Creater
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/5/5 14:20
  • 上次更新2023/10/23 16:36:56
查看原帖
关于二分图匈牙利算法的复杂度
122836
World_Creater楼主2023/5/5 14:20

众所周知匈牙利算法的复杂度 O(nm)\mathcal{O}(nm)。

但是这个上界在稀疏图好像很难跑到(尤其是加入一点随机扰动像是随机钦定左部点的顺序)。

有没有什么方法可以在稀疏图下构造达到这个上界吗?

2023/5/5 14:20
加载中...