[SOLVED] 代写 R C algorithm math parallel graph statistic network security Quiz Summary

Quiz Summary
The University of Sydney
Page 1
Quiz 3 Assignment 3
Fri 1 November 2019 (Week 12) Sun 3 November 2019, 11:59PM

Dynamic Programming Summary
– 1D dynamic programming
– Weighted interval scheduling
– Segmented Least Squares
– Maximum-sum contiguous subarray – Longest increasing subsequence
– 2D dynamic programming – Knapsack
– Longest common subsequence – Shortest path
– Dynamic programming over intervals
– RNA Secondary Structure The University of Sydney
Not Examined
Page 2

Flow networks I
The University of Sydney
Page 3

Soviet Rail Network, 1955
The University of Sydney
Page 4
Reference: On the history of the transportation and maximum flow problems. Alexander Schrijver in Math Programming, 91: 3, 2002.
4

Maximum Flow and Minimum Cut
– Max flow and min cut.
– Two very rich algorithmic problems.
– Cornerstone problems in combinatorial optimization.
– Mathematical duality.
– Nontrivial applications / reductions.
– Data mining.
– Open-pit mining.
– Project selection.
– Airline scheduling.
– Bipartite matching.
– Baseball elimination.
– Image segmentation.
– Network connectivity.
– Network reliability.
– Distributed computing.
– Egalitarian stable matching.
– Securityofstatisticaldata.
– Network intrusion detection.
– Multi-camera scene reconstruction.
– Manymanymore…
The University of Sydney
Page 5

Minimum Cut Problem
– Flow network
– Abstraction for material flowing through the edges. – G = (V, E) = directed graph, no parallel edges.
– Two distinguished nodes: s = source, t = sink.
– c(e) = capacity of edge e.
295
10
15 15
sources 5 3 8 6 10 tsink
4
10
capacity
The University of Sydney
Page 6
15
46
10
15 4 30 7

Cuts
Definitions:
– Ans-tcutisapartition(A,B)ofVwithsÎAandtÎB.
– The capacity of a cut (A, B) is: cap(A, B) = 295
å c(e) e out of A
10
4
15 15
10
s 5 3 8 6 10 t A
15
46
10
15 4 30 7
Capacity = 10 + 5 + 15
The University of Sydney
= 30
Page 7

Cuts
Definitions:
– Ans-tcutisapartition(A,B)ofVwithsÎAandtÎB.
– The capacity of a cut (A, B) is: cap(A, B) = 2 9 5
10
å c(e) e out of A
15 15
s 5 3 8 6 10 t
4
10
A
The University of Sydney
15 4 30 7
15
46
10
Capacity = 9 + 15 + 8 + 30
= 62
Page 8

Minimum Cut Problem
Min s-t cut problem:
Find an s-t cut of minimum capacity.
295
10
15 15
sources 5 3 8 6 10 tsink
4
10
15
46
10
15 4 30 7
The University of Sydney
Page 9

Minimum Cut Problem
Min s-t cut problem:
Find an s-t cut of minimum capacity.
2 9 5
10
4
15
s 5 3 8 6 10 t
15
10
A
The University of Sydney
15
46
4 30 7
10
15
Capacity = 10 + 8 + 10
= 28
Page 10

Flows
– Definition: An s-t flow is a function that satisfies: – For each e Î E: 0 £ f(e) £ c(e)
(capacity) (conservation)
– For each v Î V – {s, t}: å f(e) = e in to v
– Definition: The value of a flow f is: 0
å f (e) . e out of s
0
10
å f(e) e out of v
v( f ) = 2 9 5
4
10
0
15 15 0
44 044
s 5 3 8 6 10 t
capacity
flow
15
0
0
40 6 150
0
0
10
The University of Sydney
4 30 7
Value =Pa4ge 11

Flows
– Definition: An s-t flow is a function that satisfies: – For each e Î E: 0 £ f(e) £ c(e)
(capacity) (conservation)
– For each v Î V – {s, t}: å f(e) = e in to v
– Definition: The value of a flow f is: 6
å f (e) . e out of s
6
10
å f(e) e out of v
v( f ) = 2 9 5
10
10
0
15 15 0
44 388
s 5 3 8 6 10 t
capacity
flow
15
11
1
40 6 150
11
10
10
The University of Sydney
4 30 7
Value =P2ag4e 12

Maximum Flow Problem
– Max flow problem. Find s-t flow of maximum value.
9
2 9 5
10
10
1
15 15 0
9
10
40 489
s 5 3 8 6 10 t
capacity
flow
15
14
4
40 6 150
14
10
10
The University of Sydney
4 30 7
Value =P2ag8e 13

Flows and Cuts
– Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
åf(e) – åf(e) = v(f) e out of A e in to A
6
2 9 5
10
10
44
0
15 15 0
6
10
388
s 5 3 8 6 10 t
The University of Sydney
4 30 7
Value =P2ag4e 14
A
1
40 6 150
11
10
10
15
11

Flows and Cuts
– Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
åf(e) – åf(e) = v(f) e out of A e in to A
6
2 9 5
10
10
44
0
15 15 0
6
10
388
s 5 3 8 6 10 t
A
1
40 6 150
11
10
10
15
11
Value = 6 + 0 + 8 – 1 + 11 = 24 Page 15
The University of Sydney
4 30 7

Flows and Cuts
– Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
åf(e) – åf(e) = v(f) e out of A e in to A
6
2 9 5
10
10
44
0
15 15 0
6
10
388
s 5 3 8 6 10 t
A
1
40 6 150
11
10
10
15
11
Value = 10 – 4 + 8 – 0 + 10 = 24 Page 16
The University of Sydney
4 30 7

Flows and Cuts
– Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
– Proof:
by flow conservation, all terms except v = s are 0 i.e. fout(v) – fin(v) = 0
The University of Sydney
åf(e) – åf(e) = v(f) e out of A e in to A
v(f)= åf(e) e out of s
= å æ å f(e) – å f(e)ö
v ÎA
çè
e out of v e in to v
÷ø
= åf(e)- åf(e). e out of A e in to A
Page 17

Flows and Cuts
– Flow value ≤ cut. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut.
Cut capacity = 30 Þ Flow value £ 30 2 9 5
10
4
15 15
10
s 5 3 8 6 10 t A
15
46
10
15 4 30 7
The University of Sydney
Capacity = P3ag0e 18

Flows and Cuts
– Max flow value ≤ cut (weak duality). Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut (v(f) £ cap(A, B)).
– Proof: v(f) =
å f(e)- å f(e)
e out of A
å f(e)
å c(e) e out of A
e in to A
£
£
= cap(A,B)
A
4
8
7
6
B
t
e out of A
s
The University of Sydney
Page 19

Certificate of Optimality
Corollary: Let f be any flow, and let (A, B) be any cut.
If v(f) = cap(A, B), then f is a max flow and (A, B) is a min cut.
Value of flow = 28
Cut capacity = 28 Þ Flow value £ 28
9
2 9 5
10
10
1
15 15 0
9
10
40 489
s 5 3 8 6 10 t
4
A 15 40 6 150
10
10
The University of Sydney
4 30 7
Page 20
14
14

Towards a Max Flow Algorithm
Greedy algorithm.
– Startwithf(e)=0foralledgeeÎE.
– Find an s-t path P where each edge has f(e) < c(e).– Augment flow along path P.– Repeat until you get stuck. 10020 10s 300 t10 2000Flow value = 0 The University of SydneyPage 212 Towards a Max Flow AlgorithmGreedy algorithm.– Startwithf(e)=0foralledgeeÎE.– Find an s-t path P where each edge has f(e) < c(e).– Augment flow along path P.– Repeat until you get stuck. 1 s s3 0 X0 2 0t t20 X02001010020X0 2 0Flow value = 20 The University of SydneyPage 222 Towards a Max Flow AlgorithmGreedy algorithm.– Startwithf(e)=0foralledgeeÎE.– Find an s-t path P where each edge has f(e) < c(e). – Augment flow along path P.– Repeat until you get stuck.1120 0 20 1020 10 20 10s 3020 t s 3010 t10 20 10 200 20 10 2022TgherUeniverdsityof=Syd2ne0y opt = 30 Page 23 Residual Graph– Originaledge: e=(u,v) ÎE. – Flowf(e),capacityc(e).– Residualedge.– “Undo”flowsent.– e=(u,v)andeR =(v,u). – Residualcapacity:c(e)=ìíc(e)-f(e) ifeÎEf î f (e) if eR Î E– Residual graph: Gf = (V, Ef ).– Residualedgeswithpositiveresidualcapacity. – Ef ={e:f(e) 0}.
capacity
u 17 v
6
flow
residualcapacity
u 11 v
6
residual capacity
The University of Sydney
Page 24

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P, f) = minimum residual capacity of any edge on P with respect to the current flow f.
u s 20/30
G
20/20
t
0/10
0/10
s
v
20/20
v
u Gf
t
The University of Sydney
Page 25

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P, f) = minimum residual capacity of any edge on P with respect to the current flow f.
u s 20/30
G
20/20
t
0/10
0/10
v
u Gf 10
20/20
20
s 10
v
20 10
t 20
The University of Sydney
Page 26

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P, f) = minimum residual capacity of any edge on P with respect to the current flow f.
u s 20/30
G
Augment(f,P) {
b ¬ bottleneck(P,f) foreach e =(u,v) Î P {
if e is a forward edge then
increase f(e) in G by b
else (e is a backward edge)
decrease f(e) in G by b
}
return f }
20/20
t
0/10
0/10
v
u Gf 10
20/20
20
s 10
v bottleneck
20 10
t 20
The University of Sydney
Page 27

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P, f) = minimum residual capacity of any edge on P with respect to the current flow f.
u s 10/30
G
Augment(f,P) {
b ¬ bottleneck(P,f) foreach e =(u,v) Î P {
if e is a forward edge then
increase f(e) in G by b
else (e is a backward edge)
decrease f(e) in G by b
}
return f }
20/20
t
10/10
10/10
v
u Gf 10
20/20
20
s 10
v
20 10
t 20
The University of Sydney
Page 28
Augment(f,P) gives a new flow f’ in G

Ford-Fulkerson Algorithm
Ford-Fulkerson(G, s, t) { foreache Î E f(e) ¬ 0 Gf ¬ residual graph
while (there exists augmenting path P) {
f ¬ Augment(f, P)
update Gf }
return f }
Augment(f, P) {
b ¬ bottleneck(P) foreach e Î P {
if(e Î E)f(e) ¬ f(e)+b
else f(eR) ¬ f(e) – b }
return f }
The University of Sydney
Page 29
forward edge reverse edge

Ford-Fulkerson Algorithm
244
10 2 8 6 10
s 10 3 9 5 10 t
G:
capacity
The University of Sydney Page 30

Ford-Fulkerson Algorithm
0
2 4 4
flow
capacity
G:
s 10 3 9 5 10 t
0 10208 6010
00 000
The University of Sydney
Page 31
Flow value = 0

Ford-Fulkerson Algorithm
0
2 4 4
flow
capacity
G:
s 10 3 9 5 10 t
0 10208 6010
8X0 0 X8
0 0 8X0
Flow value = 0
244
residual capacity 10
Gf:
10
2
86
s 10 3 9 5 10 t
The University of Sydney
Page 32

Ford-Fulkerson Algorithm
G:
0
2 4 4
1 0 X8 8
10208 6010
s 10 3 X 5 t 9 10
X
0 2 02 10X8
0
2 4 4
Flow value = 8
Gf:
8
2
86
10
2 s 10 3
9 5 2 t 8
The University of Sydney
Page 33

Ford-Fulkerson Algorithm
G:
0
2 4 4
X0 6 1022 X10
X06
s 10 3 X 5
2 4 4
10 2 8 6 10
10 8
860
28
9 10
t
Flow value = 10
6 10
Gf:
s 10 3 7 5 10 t 2
The University of Sydney
Page 34

Ford-Fulkerson Algorithm
2 4 4
02 X
G:
s 10 3 9 5 10 t
X6 8 10 22 8 66 10
10 8 X0
X68 8 10
Flow value = 16
Gf:
2 4 4
10 2 8 6 4
6
s 4 3 1 5 10 t
The University of Sydney
Page 35
6
8

Ford-Fulkerson Algorithm
G:
23 X
2 4 4
X8 9 10 20 8 66 10
10 87 X
X8 9 8 9 1 0 s 10 3 X 5
t
Flow value = 18
8
9 10
Gf:
2
2 2 4
10 2 8 6 2
s 2 3 1 5 10 t
The University of Sydney
Page 36
8
8

Ford-Fulkerson Algorithm
3
2 4 4
G:
s 10 3 9 5 10 t
9 10 20 8 66 10
10 7
9 9 10
3
2 1 4
Gf: 1 9
Flow value = 19
10 2 7
6 1
s 1 3 9 5 10 t 9
The University of Sydney
Page 37

Ford-Fulkerson Algorithm
3
2 4 4
G:
s 10 3 9 5 10 t
9 10 20 8 66 10
10 7
9 9 10
Cut capacity = 19 Flow value = 19
3
2 1 4
Gf: 1 9
10 2 7
6 1
s 1 3 9 5 10 t 9
The University of Sydney
Page 38

Augmenting Path Algorithm
Ford-Fulkerson(G, s, t) { foreache Î E f(e) ¬ 0 Gf ¬ residual graph
while (there exists augmenting path P) {
f ¬ Augment(f, P)
update Gf }
return f }
Augment(f, P) {
b ¬ bottleneck(P) foreach e Î P {
if(e Î E)f(e) ¬ f(e)+b
else f(eR) ¬ f(e) – b }
return f }
The University of Sydney
Page 39
forward edge reverse edge

Max-Flow Min-Cut Theorem
Augmenting path theorem: Flow f is a max flow if and only if there are no augmenting paths.
Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. [Ford-Fulkerson 1956]
Proof strategy: We prove both simultaneously.
(i) There exists a cut (A, B) such that v(f) = cap(A, B).
(ii) Flow f is a max flow.
(iii) There is no augmenting path relative to f.
– (i) Þ (ii) This was the corollary to weak duality (flow value ≤ cut) lemma.
– (ii) Þ (iii) We show contrapositive.
– Letfbeaflow.Ifthereexistsanaugmentingpath,thenwecanimprovef
by sending flow along path.
The University of Sydney Page 40

Proof of Max-Flow Min-Cut Theorem
– (iii) Þ (i)
– Let f be a flow with no augmenting paths.
– Let A be set of vertices reachable from s in residual graph. – BydefinitionofA,sÎA.
– Bydefinitionoff,tÏA.
v(f) = =
åf(e)- åf(e)
e out of A
å c(e)
e in to A
A
B
e out of A
= cap(A,B)
t
s
The University of Sydney
original network
Page 41

Running Time
Assumption. All capacities are integers between 1 and C.
Invariant. Every flow value f(e) and every residual capacities cf (e) remains an
integer throughout the algorithm.
Theorem. The algorithm terminates in at most v(f*) £ nC augmenting paths, where f* is a max flow.
Proof: Each augmentation increase value by at least 1.
Corollary. The running time of Ford–Fulkerson is O(m n C). If C = 1, Ford-
Fulkerson runs in O(mn) time.
Proof: Can use either BFS or DFS to find an augmenting path in O(m) time.
Integrality theorem. If all capacities are integers, then there exists a max flow f for which every flow value f(e) is an integer.
Proof: Since algorithm terminates, theorem follows from invariant.
The University of Sydney Page 42

Choosing Good Augmenting Paths
The University of Sydney Page 44

Ford-Fulkerson: Exponential Number of Augmentations
– Question: Is generic Ford-Fulkerson algorithm polynomial in
input size?
– Answer: No. If max capacity is C, then algorithm can take C iterations.
11
1 X0 0 1 X0 X0 1
CCCC
s 1X01 t s 1X0X10 t
CCCC
0 0 10 X01 X1X
m, n, and C
22
The University of Sydney
Page 45

Choosing Good Augmenting Paths
– Use care when selecting augmenting paths.
– Some choices lead to exponential algorithms.
– Clever choices lead to polynomial algorithms.
– If capacities are irrational, algorithm not guaranteed to terminate!
– Goal: choose augmenting paths so that: – Can find augmenting paths efficiently.
– Few iterations.
– Choose augmenting paths with: [Edmonds-Karp 1972, Dinitz 1970] – Max bottleneck capacity.
– Sufficiently large bottleneck capacity.
– Fewest number of edges.
The University of Sydney Page 46

Capacity Scaling
– Intuition. Choosing path with highest bottleneck capacity increases flow by max possible amount.
– Don’t worry about finding exact highest bottleneck path.
– Maintain scaling parameter D.
– Let Gf (D) be the subgraph of the residual graph consisting of only arcs with capacity at least D.
44
110 102
110 102
s1ts t 122 170 122 170
22
Gf Gf (100)
The University of Sydney
Page 47

Capacity Scaling
Scaling-Max-Flow(G, s, t) { foreache Î E f(e) ¬ 0
D ¬ smallest power of 2 greater than or equal to C Gf ¬ residual graph
while (D 3 1) {
Gf(D) ¬ D-residual graph
while (there exists augmenting path P in Gf(D)) {
f ¬ augment(f, P)
update Gf(D) }
D¬D/2 }
return f }
The University of Sydney Page 48

Capacity Scaling: Correctness
– Assumption. All edge capacities are integers between 1 and C. – Integrality invariant. All flow and residual capacity values are
integral.
– Correctness. If the algorithm terminates, then f is a max flow.
Proof:
– By integrality invariant, when D = 1 Þ Gf(D) = Gf.
– Upon termination of D = 1 phase, there are no augmenting paths. ▪
The University of Sydney Page 49

Capacity Scaling: Running Time
Lemma 1. The outer while loop repeats 1 + élog2 Cù times. Proof: Initially C £ D < 2C. D decreases by a factor of 2 eachiteration. ▪Lemma 2. Let f be the flow at the end of a D-scaling phase.Then the value of the maximum flow is at most v(f) + m D.proof on next slideLemma 3. There are at most 2m augmentations per scaling phase.– Let f be the flow at the end of the previous scaling phase.– Lemma2 Þ v(f*) £ v(f)+m(2D).– Each augmentation in a D-phase increases v(f) by at least D. ▪Theorem. The scaling max-flow algorithm finds a max flow in O(m log C) augmentations. It can be implemented to run in O(m2 log C) time. ▪The University of SydneyPage 50Capacity Scaling: Running Time– Lemma 2. Let f be the flow at the end of a D-scaling phase. Then value of the maximum flow is at most v(f) + m D.– Pf. (almost identical to proof of max-flow min-cut theorem)– We show that at the end of a D-phase, there exists a cut (A, B) such thatcap(A, B) £ v(f) + m D.– Choose A to be the set of nodes reachable from s in Gf(D).– BydefinitionofA,sÎA.– Bydefinitionoff,tÏA.v(f) = å f(e)- å f(e)e out of A e in to A3 å(c(e)-D)-åDe out of A e in to A= åc(e)-åD-åDAB t e out of A e out of A 3 cap(A, B) – mDe in to AsThe University of SydneyPage 51original networkNot Examined ApplicationsThe University of SydneyPage 52– Bipartite matching– Perfect matching– Disjoint paths– Network connectivity – Image segmentation – Circulation problems Bipartite MatchingThe University of Sydney Page 53 Matching– Input: undirected graph G = (V, E).– M Í E is a matching if each node appears in at most one edgein M.– Max matching: find a max cardinality matching.The University of Sydney Page 54 Bipartite Matching– Input: undirected, bipartite graph G = (L È R, E).– M Í E is a matching if each node appears in at most one edgein M.– Max matching: find a max cardinality matching.1 1′ 2 2’3 3′ 4 4’L5 5’R matching 1-2′, 3-1′, 4-5′ The University of SydneyPage 55 Bipartite Matching– Input: undirected, bipartite graph G = (L È R, E).– M Í E is a matching if each node appears in at most one edgein M.– Max matching: find a max cardinality matching.1 1′ 2 2’3 3′ 4 4’L5 5’R max matching 1-1′, 2-2′, 3-3′ 5-5′ The University of SydneyPage 56 Bipartite MatchingMax flow formulation.– Create digraph G’ = (L È RÈ {s, t}, E’ ).– Direct all edges from L to R, and assign infinite (or unit) capacity.– Add source s, and unit capacity edges from s to each node in L.– Add sink t, and unit capacity edges from each node in R to t. G’11 ¥ 1′ 2 2’3 3′ 4 4’1stThe University of SydneyL 5 5′ RPage 57Bipartite Matching: Proof of CorrectnessTheorem: Max cardinality matching in G Û value of max flow in G’. Proof: Þ– Given max matching M of cardinality k.– Consider flow f that sends 1 unit along each of k paths. – f is a flow, and has cardinality k.1 1′ 1¥1’2 2′ 12 2’1G3 3’s33’tG’ 4 4′ 4 4′ The Univers5ity of Sydney 5′ 5 5′ Page 58 Bipartite Matching: Proof of CorrectnessTheorem: Max cardinality matching in G Û value of max flow in G’. Proof: Ü– LetfbeamaxflowinG’ofvaluek.– Integrality theorem Þ k is integral and can assume f is 0-1. – ConsiderM=setofedgesfromLtoRwithf(e)=1.• each node in L and R participates in at most one edge in M • |M|=k: considercut(LÈs,RÈt) ▪1¥1′ 1 1′ 12 2’1 2 2’s 3 3′ t 3 3′ 4 4′ 4 4’G’5 5′ 5 5’G The University of Sydney Page 59 Perfect MatchingDefinition: A matching M Í E is perfect if each node appears in exactly one edge in M.Question: When does a bipartite graph have a perfect matching?Structure of bipartite graphs with perfect matchings. – Clearly we must have |L| = |R|.The University of SydneyPage 60 Perfect MatchingNotation: Let S be a subset of nodes, and let N(S) be the set of nodes adjacent to nodes in S.Observation. If a bipartite graph G = (L È R, E), has a perfect matching, then |N(S)| 3 |S| for all subsets S Í L.Proof: Each node in S has to be matched to a different node in N(S).1 1’2 2’3 3’4 4′ No perfect matching: S = { 2, 4, 5 }N(S) = { 2′, 5′ }.The University of Sydney L 5 5′ R Page 61 Marriage TheoremMarriage Theorem. Let G = (L È R, E) be a bipartite graph with |L| = |R|. Then, G has a perfect matching iff |N(S)| 3 |S| for all subsets S Í L. [Frobenius 1917, Hall 1935]– Proof: Þ This was the previous observation.1 1’2 2’3 3’4 4′ No perfect matching: S = { 2, 4, 5 }N(S) = { 2′, 5′ }.The University of Sydney L 5 5′ R Page 62Proof of Marriage Theorem– Proof: Ü Suppose G does not have a perfect matching. – Formulate as a max flow problem and let (A, B) be min cut in G’.– Bymax-flowmin-cut,cap(A,B)<|L|.– DefineLA =LÇA, LB =LÇB, RA =RÇA.– cap(A,B) = |LB|+|RA|.– Since min cut can’t use ¥ edges: N(LA) Í RA.– |N(LA)|£|RA| = cap(A,B)-|LB| < |L|-|LB| = |LA|. – ChooseS=LA. ▪ 1G’ 1¥¥13’4′ t LA = {2, 4, 5} LB = {1, 3}RA = {2′, 5′} N(LA) = {2′, 5′}A21’¥2’1 s43The University of Sydney55’1Page 63Not Examined Bipartite Matching: Running TimeWhich max flow algorithm to use for bipartite matching? – Generic augmenting path: O(mC) = O(mn).– Capacity scaling: O(m2 log C ) = O(m2 log n).– Shortest augmenting path: O(m n1/2).Non-bipartite matching.– Structure of non-bipartite graphs is more complicated, butwell-understood.– Blossom algorithm: O(n4).– Best known: O(m n1/2).[Tutte-Berge, Edmonds-Galai] [Edmonds 1965] [Micali-Vazirani 1980]The University of SydneyPage 64