Round Trip Location on a Tree Graph.

Abstract

In this paper we consider the problem of locating a single facility on a tree graph so as to minimize the maximum 'round trip' distance from this facility to a given set of node pairs. The node pairs might represent a neighborhood and a hospital or a neighborhood and a police station to which service must be provided. Each node pair can be assigned a weight which represents the relative amount of service which must be provided at that node pair to the total amount of estimated service. In the case where all of the weights are equal we provide the results necessary to justify a simple O(m) procedure for finding an optimal location, where m is the number of node pairs. When the weights are unequal an O((n+m)lgn + mlgm) procedure for finding an optimal location is presented where n is the number of nodes in the tree graph. The classical one center problem on a tree graph is a special case of this problem. Examples and references to related research are included. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1979
Accession Number
ADA090638

Entities

People

  • Robert V. Nagelhout

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Ambulances
  • Computational Complexity
  • Hospitals
  • Intervals
  • Iterations
  • Linear Programming
  • Matrix Games
  • Military Research
  • Notation
  • Slope
  • Universities
  • Vehicles

Readers

  • Computer Networking
  • Facility/Structural Engineering.
  • Graph Algorithms and Convex Optimization.