Fast parallel algorithm for finding the kth longest path in A tree

Hong Shen

Fast parallel algorithm for finding the kth longest path in A tree

Hong Shen

Griffith University Queensland

研究成果: Paper › 同行評審

2 引文斯高帕斯（Scopus）

摘要

We present a fast parallel algorithm running in O(log ²n) time on a CREW PRAM with O(n) processors for finding the kth longest path in a given tree of n vertices (with Θ(n ²) intervertex distances). Our algorithm is obtained by efficient parallelization of a sequential algorithm which is a variant of both Megiddo et al's algorithm [12] and Fredrickson et al's algorithm [3] based on centroid decomposition of tree and succinct representation of the set of intervertex distances. With the same time and space bound as the best known result, our sequential algorithm maintains a shorter length of the decomposition tree.

原文	English
頁面	164-169
頁數	6
出版狀態	Published - 1997
對外發佈	是
事件	Proceedings of the 1997 Conference on Advances in Parallel and Distributed Computing - Shanghai, China 持續時間: 19 3月 1997 → 21 3月 1997

Conference

Conference	Proceedings of the 1997 Conference on Advances in Parallel and Distributed Computing
城市	Shanghai, China
期間	19/03/97 → 21/03/97

其它文件與鏈接

Link to publication in Scopus

引用此

@conference{438e3864876c49cba833c1670907e11f,

title = "Fast parallel algorithm for finding the kth longest path in A tree",

abstract = "We present a fast parallel algorithm running in O(log 2n) time on a CREW PRAM with O(n) processors for finding the kth longest path in a given tree of n vertices (with Θ(n 2) intervertex distances). Our algorithm is obtained by efficient parallelization of a sequential algorithm which is a variant of both Megiddo et al's algorithm [12] and Fredrickson et al's algorithm [3] based on centroid decomposition of tree and succinct representation of the set of intervertex distances. With the same time and space bound as the best known result, our sequential algorithm maintains a shorter length of the decomposition tree.",

author = "Hong Shen",

year = "1997",

language = "English",

pages = "164--169",

note = "Proceedings of the 1997 Conference on Advances in Parallel and Distributed Computing ; Conference date: 19-03-1997 Through 21-03-1997",

}

TY - CONF

T1 - Fast parallel algorithm for finding the kth longest path in A tree

AU - Shen, Hong

PY - 1997

Y1 - 1997

N2 - We present a fast parallel algorithm running in O(log 2n) time on a CREW PRAM with O(n) processors for finding the kth longest path in a given tree of n vertices (with Θ(n 2) intervertex distances). Our algorithm is obtained by efficient parallelization of a sequential algorithm which is a variant of both Megiddo et al's algorithm [12] and Fredrickson et al's algorithm [3] based on centroid decomposition of tree and succinct representation of the set of intervertex distances. With the same time and space bound as the best known result, our sequential algorithm maintains a shorter length of the decomposition tree.

AB - We present a fast parallel algorithm running in O(log 2n) time on a CREW PRAM with O(n) processors for finding the kth longest path in a given tree of n vertices (with Θ(n 2) intervertex distances). Our algorithm is obtained by efficient parallelization of a sequential algorithm which is a variant of both Megiddo et al's algorithm [12] and Fredrickson et al's algorithm [3] based on centroid decomposition of tree and succinct representation of the set of intervertex distances. With the same time and space bound as the best known result, our sequential algorithm maintains a shorter length of the decomposition tree.

UR - http://www.scopus.com/inward/record.url?scp=0030784349&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0030784349

SP - 164

EP - 169

T2 - Proceedings of the 1997 Conference on Advances in Parallel and Distributed Computing

Y2 - 19 March 1997 through 21 March 1997

ER -

Fast parallel algorithm for finding the kth longest path in A tree

摘要

Conference

其它文件與鏈接

指紋

引用此