Title :
Efficient Algorithms for Finding a Trunk on a Tree Network and Its Applications
Author :
Li, Yamin ; Peng, Shietung ; Chu, Wanming
Author_Institution :
Hosei Univ., Tokyo
Abstract :
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 EREW PRAM model. We also present an application of trunk for efficient multicast in wireless ad hoc networks.
Keywords :
computational complexity; minimisation; multicast communication; parallel algorithms; trees (mathematics); wireless sensor networks; EREW PRAM model; edge-weighted tree; multicast efficiency; parallel algorithm; sequential algorithm; tree network; trunk; wireless ad hoc networks; Application software; Computer networks; Computer science; Concurrent computing; Distributed computing; Hardware; Mobile ad hoc networks; Multicast algorithms; Parallel algorithms; Phase change random access memory;
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies, 2007. PDCAT '07. Eighth International Conference on
Conference_Location :
Adelaide, SA
Print_ISBN :
0-7695-3049-4
DOI :
10.1109/PDCAT.2007.10
