Preflow-Push: Improvement of Fold-Fulkerson

  1. Preflow-Push algorithm.
  2. Proof that if "f" is a preflow and "h" is a compatible node labeling, then there is no "s-t" path in the augmentation graph $G_f$ defined from f.
  3. Details of the Preflow-Push algorithm.
  4. Time analysis of the Preflow-Push algorithm. Bounding the number of relabels and saturating pushes
  5. Bounding the number of non-saturating pushes.
  6. Reducing the time bound by picking the node with maximum height among the nodes with excess.
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 双节快乐
    2017年9月30日 星期六 深圳 天气 晴 今天是多么美好的一天啊！充满着爱！热情！效益！感恩！Pow...
    dm小梅阅读 2,875评论 0赞 0
  • 我和我的大学四年
    于千万人之中遇见你所要遇见的人，于千万年之中，时间无涯的荒野里，没有早一步，也没有晚一步，刚巧赶上了，那也没有别的...
    忘忧的撒哈拉阅读 1,937评论 0赞 1
  • 在马尔代夫索尼娃贾尼岛，我们找到了传说中的天堂电影院
    人间天堂 走过千山万水、带着勇敢的心 走向世界尽头、带着一样热爱的你 你的一生可能会设定，很多的目的地 遥远的国度...
    猴菇旅行历险记阅读 5,278评论 0赞 1
  • 早安，重庆
    又是新的一周，群里讨论了牙膏面膜的广告阴谋论，其实忽略了这些内容强大的心理暗示作用。如果一切都回归本质，其实人只要...
    王小悠阅读 1,755评论 0赞 0