THE OPTIMAL LOCATION OF A STRUCTURED FACILITY IN A TREE NETWORK
作者:
SHIETUNG PENG,
WIN-TSUNG LO,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 1994)
卷期:
Volume 2,
issue 1-2
页码: 43-60
ISSN:1063-7192
年代: 1994
DOI:10.1080/10637199408915406
出版商: Taylor & Francis Group
关键词: distancesum;eccentricity;EREW PRAM;Location theory;parallel algorithm;tree network;tree contraction;F.2.2
数据来源: Taylor
摘要:
Efficient parallel algorithms for finding an optimal path-shaped or tree-shaped facility with a specified size in a tree network are presented. Four kinds of optimization criteria are considered: minimizing/maximizing distancesum/eccentricity. There are eight cases when considering facility shapes and optimization criteria. Parallel algorithms for finding a minimum/maximum distancesum path were presented in [9]. The other six cases are studied in this paper. Two of these six cases can be solved optimally in linear Time x Processor complexity. For the problem of finding a maximum distancesum tree, the algorithm presented in this paper is the first polynomial time solution under a reasonable assumption.
点击下载:
PDF (329KB)
返 回