A SIMPLE OPTIMAL PARALLEL ALGORITHM FOR A CORE OF A TREE

Authors
PENG ST LO WT
Citation
St. Peng et Wt. Lo, A SIMPLE OPTIMAL PARALLEL ALGORITHM FOR A CORE OF A TREE, Journal of parallel and distributed computing, 20(3), 1994, pp. 388-392
Citations number
18
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Journal of parallel and distributed computing → ACNP
ISSN journal
07437315
Volume
20
Issue
3
Year of publication
1994
Pages
388 - 392
Database
ISI
SICI code
0743-7315(1994)20:3<388:ASOPAF>2.0.ZU;2-S
Abstract
A core of a tree T = (V, E) is a path in T which minimizes SIGMA(v is- an-element-of V) d(v, P), where d(v, P), the distance from a vertex v to path P, is defined as min(u is-an-element-of p) d(v, u). We present an optimal parallel algorithm to find a core of T in O(log n) time us ing O(n/log n) processors on an EREW PRAM machine, where n is the numb er of vertices of tree T. (C) 1994 Academic Press, Inc.