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 Mathematics, Computer Science & Engineering > Computer Science
Date Deposited: 28 Oct 2020 15:11
Text - Accepted Version
Download (264kB) | Preview



Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login