𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a proposed divide-and-conquer minimal spanning tree algorithm

✍ Scribed by Ivan Stojmenović; Michael A. Langston

Publisher
Springer Netherlands
Year
1988
Tongue
English
Weight
226 KB
Volume
28
Category
Article
ISSN
0006-3835

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An O(n2) Divide-and-Conquer Algorithm fo
An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
✍ A. Ehrenfeucht; H.N. Gabow; R.M. Mcconnell; S.J. Sullivan 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 526 KB

This paper presents a simple divide-and-conquer algorithm for computing the prime tree decomposition of a two-structure. The algorithm runs in \(O\left(n^{2}\right)\) time, when \(n\) is the number of nodes of the two-structure. A directed or undirected graph is a special case of a two-structure, an

A clustering procedure based on the comp
A clustering procedure based on the comparison between the k nearest neighbors graph and the minimal spanning tree
✍ José Marı́a González-Barrios; Adolfo J. Quiroz 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 250 KB

We present a procedure for the identiÿcation of clusters in multivariate data sets, based on the comparison between the k nearest neighbors graph, G k , and the minimal spanning tree, MST. Our key statistic is the random quantity k := the smallest k such that G k contains the MST. Under regularity a