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

Research output: Contribution to conference › Paper › peer-review

2 Citations (Scopus)

Abstract

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.

Original language	English
Pages	164-169
Number of pages	6
Publication status	Published - 1997
Externally published	Yes
Event	Proceedings of the 1997 Conference on Advances in Parallel and Distributed Computing - Shanghai, China Duration: 19 Mar 1997 → 21 Mar 1997

Conference

Conference	Proceedings of the 1997 Conference on Advances in Parallel and Distributed Computing
City	Shanghai, China
Period	19/03/97 → 21/03/97

Cite this

@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

Abstract

Conference

Other files and links

Fingerprint

Cite this