ReyesAldasoro, C. C. ORCID: 0000000294662018 (1994). Algorithm to Compute Reduced Costs on a Graph. (Unpublished Masters thesis, Imperial College of Science Technology and Medicine)
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 Mathematics, Computer Science & Engineering > Computer Science 
Date Deposited:  28 Oct 2020 15:11 
URI:  https://openaccess.city.ac.uk/id/eprint/25086 

Text
 Accepted Version
Download (264kB)  Preview 
Export
Downloads
Downloads per month over past year
Actions (login required)
Admin Login 