×

Search anything:

# Cheriton-Tarjan Minimum Spanning tree algorithm

#### graph 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. #### Alexa Ryder

Hi, I am creating the perfect textual information customized for learning. Message me for anything.

Improved & Reviewed by:

Cheriton-Tarjan Minimum Spanning tree algorithm