The source-to-all maximum cost-to-time ratio problem is the problem of finding the maximum cost-to-time ratio path from a source node to every other node. The motivation comes from an application in large-scale linear programming. We present three algorithms for solving the problem. We give proofs of correctness and we analyze the running times. One of the algorithms is polynomial and the remaining two are pseudopolynomial. We present extensive computational results on several networks.
- Flow algorithms
ASJC Scopus subject areas
- Information Systems
- Computer Networks and Communications