Maximizing the Minimum Source-Sink Path Subject to a Budget Constraint: Another View of the Minimum Cost Flow Routine

Abstract

Consider a network in which each arc has a traversal time and a cost for increasing its traversal time. If a fixed budget is available for expenditure on arcs of the network, how does one allocate this budget among the arcs so as to maximize the length of a shortest path from source to sink. It is shown that the minimum cost flow algorithm can be used to solve this problem parametrically in the budget.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1975
Accession Number
ADA014422

Entities

People

  • D. R. Fulkerson
  • Gary Harding

Organizations

  • Cornell University

Tags

Communities of Interest

  • Air Platforms
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Engineering
  • Flow Network
  • Integrals
  • Linear Programming
  • Mathematics
  • Military Research
  • New York
  • Operations Research
  • Sequences
  • Universities

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Operations Research