A Fast Parametric Maximum Flow Algorithm. Revision,

Abstract

The classical maximum flow problem sometimes occurs in settings in which the capacities are not fixed but are functions of a single parameters, and the goal is to find the value of the parameter such that the corresponding maximum flow or minimum cut satisfies some side condition. Finding the desired parameter value requires solving a sequence of related maximum flow problems. We shoe that the recent maximum flow algorithm of Goldberg and Tarjan can be extended to solve an important class of such parametric maximum flow problems, at the cost of only a constant factor in its worst case time bound. Faster algorithms for a variety of combinational optimization problems follow from our result. Keywords: Algorithms; Data structures; Graphs; Maximum glow; Network flows; Networks.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1987
Accession Number
ADA194026

Entities

People

  • Giorgio Gallo
  • Michael D. Grigoriadis
  • Robert Tarjan

Organizations

  • Princeton University

Tags

Communities of Interest

  • Air Platforms
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Communication Networks
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Engineering
  • Linear Programming
  • Mathematical Programming
  • Optimization
  • Parametric Programming
  • Polynomials
  • Scheduling (Production)
  • Sequences
  • Simplex Method
  • Trees (Data Structures)

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research