DocumentCode
2724233
Title
Optimally locating a structured facility of a specified length in a weighted tree network
Author
Ku, Shan-Chyun ; Wang, Biing-Feng
Author_Institution
Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
fYear
1998
fDate
30 Mar-3 Apr 1998
Firstpage
370
Lastpage
374
Abstract
We propose efficient parallel algorithms on the EREW PRAM for optimally locating in a weighted tree network a tree-shaped facility of a specified length. Two optimization criteria are considered: minimum eccentricity and minimum distance sum. Let n be the number of vertices in the tree network. Both algorithms take O(log nloglog n) time using O(n) work
Keywords
computational complexity; operations research; optimisation; parallel algorithms; parallel machines; trees (mathematics); EREW PRAM; computation time; minimum distance sum; minimum eccentricity; optimal structured facility location; optimization criteria; parallel algorithms; tree-shaped facility; vertices; weighted tree network; Communication networks; Computer science; Councils; Intelligent networks; Parallel algorithms; Phase change random access memory; Polynomials; Road transportation; Transmission line theory;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Processing Symposium, 1998. IPPS/SPDP 1998. Proceedings of the First Merged International ... and Symposium on Parallel and Distributed Processing 1998
Conference_Location
Orlando, FL
ISSN
1063-7133
Print_ISBN
0-8186-8404-6
Type
conf
DOI
10.1109/IPPS.1998.669942
Filename
669942
Link To Document