✦ LIBER ✦

A Linear Time Algorithm for Finding ak-Tree Core

✍ Scribed by Akiyoshi Shioura; Takeaki Uno

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 173 KB
Volume: 23
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1996.0838

No coin nor oath required. For personal study only.

✦ Synopsis

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-tree core for a given k. ᮊ 1997

📜 SIMILAR VOLUMES

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

A linear algorithm for finding the k-bro

A linear algorithm for finding the k-broadcast center of a tree

✍ Hovhannes A. Harutyunyan; Arthur L. Liestman; Bin Shao 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

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

Efficient algorithms for finding the (k,

Efficient algorithms for finding the (k, l)-core of tree networks

✍ Ronald I. Becker; Isabella Lari; Giovanni Storchi; Andrea Scozzari 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB

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

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