City Research Online

Algorithm to Compute Reduced Costs on a Graph

Reyes-Aldasoro, C. C. ORCID: 0000-0002-9466-2018 (1994). Algorithm to Compute Reduced Costs on a Graph. (Unpublished Masters thesis, Imperial College of Science Technology and Medicine)


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
[thumbnail of T1994_AlgorithmtoComputeReducedCostsonaGraph_MScThesisReyesAldasoro.pdf]
Text - Accepted Version
Download (264kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login