City Research Online

Abstract

The problem of calculating the Reduced Costs of all arcs on a graph is considered. For each arc on the graph, the problem is to determine the arc with maximum cost on the fundamental path on the corresponding spanning tree. A new algorithm for this problem is proposed. It is based on the construction of a Binary Tree by sequential deletion of arcs in a descending order of costs. The tree is composed of leaf nodes representing the actual vertices in the graph and intermediate nodes representing the branches of the Minimum Spanning Tree. Using the Binary Tree, the Reduced Costs of any chord is determined by the Nearest Common Ancestor of the leaf nodes corresponding to the chord vertices. Computational results are presented for graphs of various densities. The algorithm's performance is compared to the path labelling algorithm of Carpaneto.

Publication Type:	Thesis (Masters)
Additional Information:	Copyright, the author, 1994.
Publisher Keywords:	Graph theory; Minimum Spanning Tree
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments:	School of Science & Technology > Computer Science School of Science & Technology > Computer Science > giCentre

Export

Downloads