REMOVING ARCS FROM A NETWORK

Abstract

This paper is concerned with a sensitivity analysis on a maximum flow network. The network is defined by a set of arcs and a set of points called nodes. Each arc joins two nodes and has associated with it a positive capacity which represents the maximum amount of flow that may pass over it. One of the nodes is designated as the source and another as the sink. Given a maximum flow network from which n arcs are to be removed, which n arcs, if removed, would reduce the maximum flow from source to sink the most and what would be the resulting maximum flow. This paper presents an algorithm for solving such a problem for a certain class of networks. The algorithm would be helpful in determining how sensitive a transportation system might be to having some of its roads closed down for repairs or tied up by traffic accidents. It might also shed light on the problem of adding arcs which is of interest in deciding where to build new roads.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 13, 1964
Accession Number
AD0601643

Entities

People

  • Richard Wollmer

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Accidents
  • Algorithms
  • California
  • Construction
  • Equations
  • Flow Network
  • Iterations
  • Mathematics
  • Motor Vehicle Accidents
  • Operations Research
  • Sensitivity
  • Transportation
  • Universities

Fields of Study

  • Computer science

Readers

  • Facility/Structural Engineering.
  • Graph Algorithms and Convex Optimization.
  • Theoretical Analysis.