Lecture slides by Kevin Wayne
Copyright © 2005 Pearson-Addison Wesley
http://www.cs.princeton.edu/~wayne/kleinberg-tardos
Last updated on 7/25/17 10:58 AM
4. G
REEDY
A
LGORITHMS
II
‣ Edmonds branching algorithm demo
Edmonds branching algorithm demo
2
r
10
6
5
2
11
3
9
7
13
1
12
8
4
input digraph G = (V, E)
Edmonds branching algorithm demo
3
r
10
6
5
2
11
3
9
7
13
1
12
8
4
2
3
12
7
9
1
10
Phase 1: find cheapest edge entering each node
Edmonds branching algorithm demo
4
r
0
4
3
0
1
0
0
0
4
0
0
7
1
2
3
12
7
9
1
10
Phase 1: replace costs with reduced costs
Edmonds branching algorithm demo
5
r
0
4
3
0
1
0
0
0
4
0
0
7
1
Phase 1: find 0-cost directed cycle C and contract
r
4
3
0
1
0
0
7
1
Edmonds branching algorithm demo
6
Phase 2: digraph G'
4
3
0
1
0
0
7
1
r
Edmonds branching algorithm demo
7
Phase 2: find cheapest edge entering each node
4
3
0
1
0
0
7
1
r
1
0
0
0
Edmonds branching algorithm demo
8
Phase 2: replace cost with reduced costs
3
2
0
1
0
0
7
0
r
1
0
0
0
Edmonds branching algorithm demo
9
Phase 2: find 0-cost directed cycle and contract
3
2
0
1
0
0
7
0
r
3
2
0
1
r
Edmonds branching algorithm demo
r
10
Phase 3: digraph G''
3
2
0
1
Edmonds branching algorithm demo
r
11
Phase 3: find cheapest edge entering each node
3
2
0
1
Edmonds branching algorithm demo
r
12
Phase 3: it's an arborescence!
3
2
0
1
Edmonds branching algorithm demo
r
13
Phase 2': uncontract node and take all but one edge of cycle
3
2
0
1
3
2
0
1
0
0
7
0
r
don't take
this edge
Edmonds branching algorithm demo
14
Phase 1': uncontract node and take all but one edge of cycle
r
r
don't take
this edge
Edmonds branching algorithm demo
15
stop: no more nodes to uncontract
r
Edmonds branching algorithm demo
16
min-cost arborescence
r
10
6
5
2
11
3
9
7
13
1
12
8
4
