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

fYear

2007

fDate

3-6 Dec. 2007

Firstpage

355

Lastpage

362

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/PDCAT.2007.10

Filename

4420190