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