Optimal Algorithms for Finding a Trunk on a Tree Network and its Applications

Authors: Li, Yamin; Peng, Shietung; Chu, Wanming

Source: Computer Journal, Volume 52, Number 2, 23 March 2009 , pp. 268-275(8)

Buy & download fulltext article:

Price: $42.29 plus tax (Refund Policy)

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 the EREW PRAM model. We present an application of trunk on mobile ad hoc networks for efficient multicasting.

Keywords: tree network; algorithm; wireless ad hoc networks

Document Type: Research article

DOI: http://dx.doi.org/10.1093/comjnl/bxn037

Publication date: 2009-03-23

More about this publication?

The Computer Journal publishes research papers in a full range of subject areas, as well as regular feature articles and occasional themed issues to enable readers to easily access information outside their direct area of research. The journal provides a complete overview of developments in the field of Computer Science.