An Algorithm to Compute Reduced Costs for Spanning Trees   Abílio Lucena; C.C. Reyes-Aldasoro & Y.M. Sharaiha 

 

The problem of computing the edge reduced costs for spanning trees is considered. Let T be a spanning tree of an undirect graph G = (V,E). An edge of G in T is called a branch, and an edge of G not in T is called a chord. For each chord (i,j) pertence E, the problem is essentially to determine a branch with maximum edge cost on the unique path linking i and j in T.

 

A new algorithm for this problem is presented. The algorithm is based on the construction of a binary tree by sequential deletion of the branches in T in a descending order of their costs. The binary tree (BT) constructed is composed of leaf nodes representing the actual vertices in the graph and intermediate nodes representing the branches of T. The problem then naturally reduces to that of locating the nearest common ancestors of the leaf nodes in BT. An analysis of the algorithm's computational complexity for complete graphs is presented. Computational results are also presented for graphs of various sizes and densities. The algorithm's computational performance is compared with an edge labelling algorithm presented in the literature.

---

  Principal | ITAM | DAI