tailieunhanh - Lecture Algorithm design - Chapter 7: Network flow I
Lecture Algorithm design - Chapter 7 "Network flow I" include all of the following: Max-flow and min-cut problems, Ford-Fulkerson algorithm, max-flow min-cut theorem, capacity-scaling algorithm, shortest augmenting paths, blocking-flow algorithm, unit-capacity simple networks. | Lecture slides by Kevin Wayne Copyright 2005 Pearson-Addison Wesley Copyright 2013 Kevin Wayne http wayne kleinberg-tardos 7. Network Flow I max-flow and min-cut problems Ford-Fulkerson algorithm max-flow min-cut theorem capacity-scaling algorithm shortest augmenting paths blocking-flow algorithm unit-capacity simple networks Last updated on Sep 8 2013 6 40 AM Section 7. Network Flow I max-flow and min-cut problems Flow network Abstraction for material flowing through the edges. Digraph G V E with source 5 G V and sink t G V. Nonnegative integer capacity c e for each e G E. no parallel edges no edge enters s no edge leaves t
đang nạp các trang xem trước