On a proposed divide-and-conquer minimal spanning tree algorithm
type: Item
instance of: scholarly article
title: On a proposed divide-and-conquer minimal spanning tree algorithm
zbMATH Open document ID: 0663.68083
DOI: 10.1007/BF01954898
author: Michael A. Langston
author: Ivan Stojmenović
published in: BIT
publication date: 1988-01-01T00:00:00Z
review text: \textit{R. Chang} and \textit{R. Lee} [ibid. 26, 7-16 (1986; Zbl 0602.68053)] purport to devise an O(N log N) time minimal spanning tree algorithm for N points in the plane that is based on a divide-and-conquer strategy using Voronoi diagrams. In this brief note, we present families of problem instances to show that the Chang-Lee worst-case timing analysis is incorrect, resulting in a time bound of \(O(N^ 2 \log N)\). Since it is known that alternate, truly O(N log N) time algorithms are available anyway, the general utility of the Chang-Lee algorithm is questionable.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4085049
zbMATH Keywords: minimal spanning tree
zbMATH Keywords: divide-and-conquer
MaRDI profile type: Publication
cites work: An O(N log N) minimal spanning tree algorithm for N points in the plane
cites work: A taxonomy of problems with fast parallel algorithms
cites work: On the shortest spanning subtree of a graph and the traveling salesman problem
cites work: Two algorithms for constructing a Delaunay triangulation
full work available at URL: https://doi.org/10.1007/bf01954898
OpenAlex ID: W2081205286
description: scientific article; zbMATH DE number 4085049