Research Reports from the Department of Operations
Document Type
Report
Publication Date
8-1-1974
Abstract
The minimal spanning tree problem is well known, and efficient algorithms exist for solving this problem. One of these algorithms has been called a "greedy" algorithm by Edmonds, who has also described the full potential of such an algorithm. In this paper, we consider a slightly modified objective function. We show that the greedy algorithm does not work for this modified problem, even if it is modified in a suitable way. First we provide a characterization for an optimal tree, which is an extension of a condition found in [2] for the minimal spanning tree problem. This gives us an improvement routine as well and thus provides an algorithm for the modified problem. We now state the problem more precisely.
Keywords
Operations research, Algorithms, Greedy algorithms, Mathematical optimization
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 339
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Chandrasekaran, R., "Minimal Spanning Trees with Ratio Criterion" (1974). Research Reports from the Department of Operations. 309.
https://commons.case.edu/wsom-ops-reports/309