Edmonds' Maximum Branching Algorithm.
Problem 1
Maximum Branching: Given a directed graph G=(V,A) and weights wa associated
to all arcs a Î A, determine a branching B, i.e. B Í A and G(B)=(V,B)
contains no cycles and has all vertices with indegree at most 1, with largest total weight.
MBA
Step 1 Initialization.
Let k=1, Vk = V, Ak = A, Gk=(Vk,Ak), p(i,j)k = (i,j), " (i,j) Î Ak.
Step 2 Greedy.
Consider graph Gk. For each vertex v Î Vk select av Î d-(v)
such that wavk is maximum. Set Bk = { wavk | wavk ³ 0}.
Step 3 Optimality test.
Test is GB = (Vk, Bk) contains cycles. If the answer is NO, stop. Bk is a
maximum weight branching for Gk, call this branching Bk*.
Recover the maximum branching for G, B1*,
by obtaining Bq-1* from Bq* repeatedly.
This is done by renaming each arc (i,j) Î Bq* by pq(i,j)
and adding all arcs in Bq that are not already in Bq* and will not violate
the branching definition (this set is unique).
Otherwise, go to the next step.
Step 4 Iteration.
Let C ={ C1, ..., Cl } denote the set of cycles
in GB, i.e. Ci Í V contains all vertices in the cycle i.
Construct Gk + 1 = (Vk + 1, Ak + 1) as follows. Let
VC be the set of all vertices that appear in C, i.e. VC = C1 È
... Cl. The vertex set is then Vk + 1 = C È { Vk - VC }.
The arc set is obtained by the union of two sets A1 and A2. The first, A1,
contains all arcs with both endpoints in Vk - VC, i.e.
A1 = { (u,w) | (u,w) Î Ak, u, v Î Vk - VC }.
To obtain the second set, first note that the weights in Gk+1 of the arcs that, in GK, arrive at a vertex
that belongs to a cycle Ci must be computed suitably. Their values must now correspond to the
contribution that the arc will give to the whole branching. Let a=(w,u), u Î Ci and w ÏCi.
Let also wmin be the smallest weight among the weight of the arcs in Ci and wu the weight of the arc that
arrives at u in GB. Then, the value of the contribution of a is given by wak+1 = wak - wu + wmin.
The set A2 is obtained by colapsing all vertices in each cycle Ci to a single vertex. For any set of multiple
arcs that may appear, i. e. set of arcs that depart from and arrive at the same vertices, keep only the one
with maximum weight. For all arcs (i,j) in Ak+1 make p(i,j)k+1 correspond to the endpoints of the
arc in GK.
Go back to step 2.
This document was translated from LATEX by HEVEA.