Edmonds’ algorithm

Posted by admin on February 13, 2018 in Uncategorized |

In graph theory, Edmonds’ algorithm or Chu–Liu/Edmonds’ algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an optimum branching). It is the directed analog of the minimum spanning tree problem. The algorithm was proposed independently first by Yoeng-Jin Chu and Tseng-Hong Liu (1965) and then by Jack Edmonds (1967).

The algorithm takes as input a directed graph





D


=






V


,


E








{\displaystyle D=\langle V,E\rangle }


where





V




{\displaystyle V}


is the set of nodes and





E




{\displaystyle E}


is the set of directed edges, a distinguished vertex




r






V




{\displaystyle r\in V}


called the root, and a real-valued weight





w


(


e


)




{\displaystyle w(e)}


for each edge





e






E




{\displaystyle e\in E}


. It returns a spanning arborescence





A




{\displaystyle A}


rooted at





r




{\displaystyle r}


of minimum weight, where the weight of an arborescence is defined to be the sum of its edge weights,





w


(


A


)


=








e






A





w


(


e


)





{\displaystyle w(A)=\sum _{e\in A}{w(e)}}


.

The algorithm has a recursive description. Let





f


(


D


,


r


,


w


)




{\displaystyle f(D,r,w)}


denote the function which returns a spanning arborescence rooted at





r




{\displaystyle r}


of minimum weight. We first remove any edge from





E




{\displaystyle E}


whose destination is





r




{\displaystyle r}


. We may also replace any set of parallel edges (edges between the same pair of vertices in the same direction) by a single edge with weight equal to the minimum of the weights of these parallel edges.

Now, for each node





v




{\displaystyle v}


other than the root, find the edge incoming to





v




{\displaystyle v}


of lowest weight (with ties broken arbitrarily). Denote the source of this edge by





π



(


v


)




{\displaystyle \pi (v)}


. If the set of edges





P


=


{


(


π



(


v


)


,


v


)






v






V






{


r


}


}




{\displaystyle P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}}


does not contain any cycles, then





f


(


D


,


r


,


w


)


=


P




{\displaystyle f(D,r,w)=P}


.

Otherwise,





P




{\displaystyle P}


contains at least one cycle. Arbitrarily choose one of these cycles and call it





C




{\displaystyle C}


. We now define a new weighted directed graph






D









=







V









,



E















{\displaystyle D^{\prime }=\langle V^{\prime },E^{\prime }\rangle }


in which the cycle





C




{\displaystyle C}


is “contracted” into one node as follows:

The nodes of






V











{\displaystyle V^{\prime }}


are the nodes of





V




{\displaystyle V}


not in





C




{\displaystyle C}


plus a new node denoted






v



C






{\displaystyle v_{C}}


.

For each edge in






E











{\displaystyle E^{\prime }}


, we remember which edge in





E




{\displaystyle E}


it corresponds to.

Now find a minimum spanning arborescence






A











{\displaystyle A^{\prime }}


of






D











{\displaystyle D^{\prime }}


using a call to





f


(



D









,


r


,



w









)




{\displaystyle f(D^{\prime },r,w^{\prime })}


. Since






A











{\displaystyle A^{\prime }}


is a spanning arborescence, each vertex has exactly one incoming edge. Let





(


u


,



v



C




)




{\displaystyle (u,v_{C})}


be the unique incoming edge to






v



C






{\displaystyle v_{C}}


in






A











{\displaystyle A^{\prime }}


. This edge corresponds to an edge





(


u


,


v


)






E




{\displaystyle (u,v)\in E}


with





v






C




{\displaystyle v\in C}


. Remove the edge





(


π



(


v


)


,


v


)




{\displaystyle (\pi (v),v)}


from





C




{\displaystyle C}


, breaking the cycle. Mark each remaining edge in





C




{\displaystyle C}


. For each edge in






A











{\displaystyle A^{\prime }}


, mark its corresponding edge in





E




{\displaystyle E}


. Now we define





f


(


D


,


r


,


w


)




{\displaystyle f(D,r,w)}


to be the set of marked edges, which form a minimum spanning arborescence.

Observe that





f


(


D


,


r


,


w


)




{\displaystyle f(D,r,w)}


is defined in terms of





f


(



D









,


r


,



w









)




{\displaystyle f(D^{\prime },r,w^{\prime })}


, with






D











{\displaystyle D^{\prime }}


having strictly fewer vertices than





D




{\displaystyle D}


. Finding





f


(


D


,


r


,


w


)




{\displaystyle f(D,r,w)}


for a single-vertex graph is trivial (it is just





D




{\displaystyle D}


itself), so the recursive algorithm is guaranteed to terminate.

The running time of this algorithm is





O


(


E


V


)




{\displaystyle O(EV)}


. A faster implementation of the algorithm due to Robert Tarjan runs in time





O


(


E


log






V


)




{\displaystyle O(E\log V)}


for sparse graphs and





O


(



V



2




)




{\displaystyle O(V^{2})}






O


(


E


+


V


log






V


)




{\displaystyle O(E+V\log V)}


.

Tags: ,

Copyright © 2015-2018 Hermes Tassen Online,Enorme Korting. All rights reserved.

Kelme Outlet | Le Coq Sport Outlet

kelme paul frank outlet new balance outlet bogner outlet le coq sportif outlet hermes tassen hermes birkin hermes online shop