Optimal Algorithms for Finding a Trunk on a Tree Network and its Applications
Yamin Li, S. Peng, Wanming Chu · The Computer Journal · 2008
Given an edge-weighted tree T, a trunk is a path P in T which minimizes the sum of the distances of all vertices in T from P plus the weight of path P. In this paper, we give efficient algorithms for finding a trunk of T. The first algorithm is a sequential algorithm which runs in O(n) time, where n is the number of vertices in T. The second algorithm is a parallel algorithm which runs in O(log n) time using O(n/log n) processors on the EREW PRAM model. We present an application of trunk on mobile ad hoc networks for efficient multicasting.