Cheriton-Tarjan Minimum Spanning tree algorithm

• Algorithm
• Complexity
• Pseudocode
• Discussion

Cheriton-Tarjan algorithm is a modification of Kruskal's algorithm designed to reduce the O(e log e) term.

Similar to Kruskal's algorithm, it grows a spanning forest, beginning with a forest of n = |G| components each consisting of a single node. Now the term O(e log e) comes from selecting the minimum edge from a heap of e edges. Since, every component Tu must eventually be connected to another component, this algorithm keeps a separate heap PQu for each component Tu, so, that initially n smaller heaps are used. Initially, PQu will contain only DEG(u) edges, since Tu consists only of vertex u. When Tu and Tv are merged, PQu and PQv must also be merged. This requires a modification of the data structures, since heaps cannot be merged efficiently. This is essentially because merging heaps reduces to building a new heap.

Any data strucutre in which a minimum element can be found efficiently is called a priority queue. A heap is one form of priority queue, in which elements are stored as an array, but viewed as a binary tree. There are many other forms of priority queue. In this algorithm, PQu will stand for a priority queue which can be merged.

It stores a list Tree of the edges of a minimum spanning tree. The components of the spanning forest are represented as Tu and the priority queue of edges incident on vertices of Tu is stored as PQu.

Complexity

The complexity of Cheriton-Tarjan minimum spanning tree algorithm is O(E log(log V)) where E is the number of edges and V is the number of vertices.

Pseudocode

Consider the following pseudo-code for Cheriton-Tarjan Minimum Spanning tree algorithm:

MST-CHERITON-TARJAN (G = (V,E), w)

Q := null                         /* A Set of edges in minimum spanning tree */
for each vertex v in  V[G]        /* V[G] is the vertex set in graph G */
     do (v belongs to Q)
          stage(v) = 0  
j = 1                             /* j is stage number which is initialized to 1 */
while |Q| > 2                     /* Number of elements in Q is greater than 2 */
     do (Q belongs to T1)         /* Let T1 be the tree in front of Q */
          if (stage(T1) == j)
               do j = j+1
                     CLEAN-UP
          find edge (u,v) in E with minimum weight such that u belongs to T1 , v belongs to `V-T1`
          let T2 be the tree in Q that contains v
          T = MERGE(T1,T2)        /* by adding edge (u,v)  to MST*/
          Q = Q-T1-T2              /* Remove T1 & T2 from Q */
          stage(T) = 1 + minimum_of{ stage(T1), stage(T2) } 
          Q = T
END

ClEAN-UP
Shrink G to G* where  G* is G with each tree shrunk to a single node and only those edges (u,v) Î G*, u Î T, vÎ T', that are shortest incident edges between disjoint T, T'.

You can read the research paper here.