TWO SENSITIVITY ANALYSIS PROBLEMS IN NETWORKS

Abstract

The paper is concerned with two sensitivity analysis problems on a network each arc of which is subject to one or to more than one reduction in its length. Suppose that a total number of s reductions can occur on the whole network. The two problems are the following: (i) Which arc should be reduced such that the shortest route from source to any node i is reduced the most. (ii) Which arcs should be reduced such that the sum of all the shortest routes between each pair of nodes is reduced the most. In (i) we generalize Dantzig's algorithm concerning the shortest route from source to sink in a graph. In (ii) we generalize Dantzig's algorithm concerning the shortest routes between each pair of nodes in a directed graph.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1968
Accession Number
AD0685829

Entities

People

  • Joseph Degrand

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Air Platforms
  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • California
  • Commodities
  • Construction
  • Dynamic Programming
  • Flow Network
  • Graphs
  • Hypotheses
  • Military Research
  • Networks
  • North Carolina
  • Operations Research
  • Security
  • Travel Time
  • United States
  • Universities

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research