Title :
The optimal location of a structured facility in a tree network
Author :
Peng, Shietung ; Lo, Win-tsung
Author_Institution :
Dept. of Comput. Sci., Maryland Univ., Baltimore, MD, USA
Abstract :
Efficient parallel algorithms for finding an optimum path-shaped or tree-shaped facility with a specified size in a tree network are presented. Four kinds of optimization criteria are considered: minimum eccentricity, maximum eccentricity, minimum distancesum, and maximum distancesum. Eight cases are obtained by combining facility shapes and optimization criteria. Optimal parallel algorithms for finding a minimum/maximum distancesum path were presented by B.C. Tansel et al. (1983). The other six cases are studied here. Two of them can be solved optimally in linear time×processor complexity. For the problem of finding a maximum distancesum tree, the algorithm presented is a polynomial time resolution
Keywords :
computational complexity; parallel algorithms; polynomials; trees (mathematics); complexity; maximum distancesum; maximum eccentricity; minimum distancesum; minimum eccentricity; optimal location; optimization criteria; optimum path shaped facility; parallel algorithms; polynomial time resolution; structured facility; tree network; tree-shaped facility; Computational modeling; Computer science; Concurrent computing; Ear; Intelligent networks; Parallel algorithms; Phase change random access memory; Polynomials; Road transportation; Shape;
Conference_Titel :
System Sciences, 1993, Proceeding of the Twenty-Sixth Hawaii International Conference on
Conference_Location :
Wailea, HI
Print_ISBN :
0-8186-3230-5
DOI :
10.1109/HICSS.1993.284104
