Algorithms for Source-to-All Maximum Cost-to-Time Ratio Problem in Acyclic Networks

Alexandra Makri, Diego Klabjan*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1-14
Number of pages14
Issue number1
StatePublished - Aug 1 2003


  • Flow algorithms
  • Graphs
  • Networks

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Algorithms for Source-to-All Maximum Cost-to-Time Ratio Problem in Acyclic Networks'. Together they form a unique fingerprint.

Cite this