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

A linear algorithm for a core of a tree

โœ Scribed by Christine A Morgan; Peter J Slater

Publisher
Elsevier Science
Year
1980
Tongue
English
Weight
565 KB
Volume
1
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

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

Algorithms for a Core and k-Tree Core of
Algorithms for a Core and k-Tree Core of a Tree
โœ S.T. Peng; A.B. Stephens; Y. Yesha ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 595 KB

We first give a one-pass algorithm for finding the core of a tree. This algorithm is a refinement of the two-pass algorithm of Morgan and Slater. We then define a generalization of a core which we call a \(k\)-tree core. Given a tree \(T\) and parameter \(k\), a \(k\)-tree core is a subtree \(T^{\pr

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 linear-time algorithm for broadcast do
A linear-time algorithm for broadcast domination in a tree
โœ John Dabney; Brian C. Dean; Stephen T. Hedetniemi ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 268 KB

## Abstract The broadcast domination problem is a variant of the classical minimum dominating set problem in which a transmitter of power __p__ at vertex __v__ is capable of dominating (broadcasting to) all vertices within distance __p__ from __v__. Our goal is to assign a broadcast power __f__(__v