Optimally locating a structured facility of a specified length in a weighted tree network

摘要

[[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