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

Efficient Algorithms for Finding a Core of a Tree with a Specified Length

โœ Scribed by Shietung Peng; Win-tsung Lo

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
176 KB
Volume
20
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 algorithm runs in O log n time using O n processors on an EREW PRAM model.

๐Ÿ“œ 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

A Simple Optimal Parallel Algorithm for
A Simple Optimal Parallel Algorithm for a Core of a Tree
โœ S.T. Peng; W.T. Lo ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 354 KB

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 usin

A Rapid Heuristic Algorithm for Finding
A Rapid Heuristic Algorithm for Finding Minimum Evolution Trees
โœ Andrew Rodin; Wen-Hsiung Li ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 69 KB

The minimum sum of branch lengths (S), or the minimum evolution (ME) principle, has been shown to be a good optimization criterion in phylogenetic inference. Unfortunately, the number of topologies to be analyzed is computationally prohibitive when a large number of taxa are involved. Therefore, sim