K-Trunk and Efficient Algorithms for Finding a K-Trunk on a Tree Network

H
HICSS
2008
Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008)
Abstract - K-Trunk and Efficient Algorithms for Finding a K-Trunk on a Tree Network

	This Article
	PDF RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	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

Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008)

K-Trunk and Efficient Algorithms for Finding a K-Trunk on a Tree Network (PDF)

Waikoloa, Big Island, Hawaii

January 07-January 10

ISBN: 0-7695-3075-3

	ASCII Text	x
	Yamin Li, Shietung Peng, Wanming Chu, "K-Trunk and Efficient Algorithms for Finding a K-Trunk on a Tree Network," Hawaii International Conference on System Sciences, pp. 472, Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008), 2008.

	BibTex	x
	@article{ 10.1109/HICSS.2008.505, author = {Yamin Li and Shietung Peng and Wanming Chu}, title = {K-Trunk and Efficient Algorithms for Finding a K-Trunk on a Tree Network}, journal ={Hawaii International Conference on System Sciences}, volume = {0}, year = {2008}, issn = {1530-1605}, pages = {472}, doi = {http://doi.ieeecomputersociety.org/10.1109/HICSS.2008.505}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Hawaii International Conference on System Sciences TI - K-Trunk and Efficient Algorithms for Finding a K-Trunk on a Tree Network SN - 1530-1605 SP EP A1 - Yamin Li, A1 - Shietung Peng, A1 - Wanming Chu, PY - 2008 KW - null VL - 0 JA - Hawaii International Conference on System Sciences ER -

Yamin Li

Shietung Peng

Wanming Chu

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/HICSS.2008.505

Given an edge-weighted tree T, a k-trunk is a subtree Tk with k leaves in T which minimizes the sum of the distances of all vertices in T from Tk plus the weight of Tk. In this paper, we first give motivation for using a k-trunk in tree networks. Then we develop efficient algorithms for finding a k-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.

Citation:

Yamin Li, Shietung Peng, Wanming Chu, "K-Trunk and Efficient Algorithms for Finding a K-Trunk on a Tree Network," hicss, pp.472, Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008), 2008

Peer Review Notice | Give Us Feedback

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