Accession Number:

AD0601643

Title:

REMOVING ARCS FROM A NETWORK

Descriptive Note:

Corporate Author:

CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER

Personal Author(s):

Report Date:

1964-03-13

Pagination or Media Count:

18.0

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.

Subject Categories:

  • Operations Research
  • Logistics, Military Facilities and Supplies

Distribution Statement:

APPROVED FOR PUBLIC RELEASE