EFFICIENT ALGORITHMS FOR FINDING A CORE OF A TREE WITH A SPECIFIED LENGTH

Authors
PENG ST LO WT
Citation
St. Peng et Wt. Lo, EFFICIENT ALGORITHMS FOR FINDING A CORE OF A TREE WITH A SPECIFIED LENGTH, Journal of algorithms, 20(3), 1996, pp. 445-458
Citations number
9
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms → ACNP
ISSN journal
01966774
Volume
20
Issue
3
Year of publication
1996
Pages
445 - 458
Database
ISI
SICI code
0196-6774(1996)20:3<445:EAFFAC>2.0.ZU;2-9
Abstract
A core of a graph G is a path P in G that is central with respect to t he property of minimizing d(P) = Sigma(v) is an element of (V(G))d(v, P), where d(v, P) is the distance from vertex upsilon to path P. This paper presents efficient algorithms for finding a core of a tree with a specified length. The sequential algorithm runs in O(n log n) time, where n is the size of the tree. The parallel algorithm runs in O(log( 2)n) time using O(n) processors on an EREW PRAM model. (C) 1996 Academ ic Press, Inc.