Efficient Algorithms for Finding a Trunk on a Tree Network and Its Applications

Adelaide, Australia December 03-December 06

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/PDCAT.2007.10

Eighth International Conference on Pa ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Yamin Li Articles by Shietung Peng Articles by Wanming Chu

	ASCII Text	x
	Yamin Li, Shietung Peng, Wanming Chu, "Efficient Algorithms for Finding a Trunk on a Tree Network and Its Applications," Parallel and Distributed Computing Applications and Technologies, International Conference on, pp. 355-362, Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2007), 2007.

	BibTex	x
	@article{ 10.1109/PDCAT.2007.10, author = {Yamin Li and Shietung Peng and Wanming Chu}, title = {Efficient Algorithms for Finding a Trunk on a Tree Network and Its Applications}, journal ={Parallel and Distributed Computing Applications and Technologies, International Conference on}, volume = {0}, year = {2007}, isbn = {0-7695-3049-4}, pages = {355-362}, doi = {http://doi.ieeecomputersociety.org/10.1109/PDCAT.2007.10}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel and Distributed Computing Applications and Technologies, International Conference on TI - Efficient Algorithms for Finding a Trunk on a Tree Network and Its Applications SN - 0-7695-3049-4 SP355 EP362 A1 - Yamin Li, A1 - Shietung Peng, A1 - Wanming Chu, PY - 2007 VL - 0 JA - Parallel and Distributed Computing Applications and Technologies, International Conference on ER -

Yamin Li

Shietung Peng

Wanming Chu

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 al- gorithm is a sequential algorithm which runs in O(n) time, where n is the number of vertices in T . The second algo- rithm 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.

Citation:

Yamin Li, Shietung Peng, Wanming Chu, "Efficient Algorithms for Finding a Trunk on a Tree Network and Its Applications," pdcat, pp.355-362, Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2007), 2007

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.