๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A Simple Optimal Parallel Algorithm for a Core of a Tree

โœ Scribed by S.T. Peng; W.T. Lo

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
354 KB
Volume
20
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

A core of a tree (T=(V, E)) is a path in (T) which minimizes (\Sigma_{v \in V}) (d(v, P)), where (d(v, P)), the distance from a vertex (v) to path (P), is defined as (\min _{u \in P} d(v, u)). We present an optimal parallel algorithm to find a core of (T) in (O(\log n)) time using (O(n / \log n)) processors on an EREW PRAM machine, where (n) is the number of vertices of tree (T). O 1994 Academic Press, Inc.

๐Ÿ“œ SIMILAR VOLUMES

Efficient Parallel Algorithms for Optima
Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network
โœ Biing-Feng Wang ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 128 KB

In this paper, we propose efficient parallel algorithms on the EREW PRAM for optimally locating in a tree network a path-shaped facility and a tree-shaped facility of a specified length. Edges in the tree network have arbitrary positive lengths. Two optimization criteria are considered: minimum ecce

A Linear Time Algorithm for Finding ak-T
A Linear Time Algorithm for Finding ak-Tree Core
โœ Akiyoshi Shioura; Takeaki Uno ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 173 KB

Given a tree containing n vertices, consider the sum of the distance between all ลฝ . vertices and a k-leaf subtree subtree which contains exactly k leaves . A k-tree core is a k-leaf subtree which minimizes the sum of the distances. In this paper, we propose a linear time algorithm for finding a k-t

Efficient Algorithms for Finding a Core
Efficient Algorithms for Finding a Core of a Tree with a Specified Length
โœ Shietung Peng; Win-tsung Lo ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 176 KB

A core of a graph G is a path P in G that is central with respect to the property 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 ลฝ 2 . ลฝ. size of the tree. The parallel alg

An Optimal Simple Parallel Algorithm for
An Optimal Simple Parallel Algorithm for Testing Isomorphism of Maximal Outerplanar Graphs
โœ Shan-Chyun Ku; Biing-Feng Wang ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 91 KB

An outerplanar graph is a planar graph that can be imbedded in the plane in such a way that all vertices lie on the exterior face. An outerplanar graph is maximal if no edge can be added to the graph without violating the outerplanarity. In this paper, an optimal parallel algorithm is proposed on th