A fast and simple algorithm for computing approximate Euclidean minimum spanning trees

DOI10.1137/1.9781611974331.CH85MaRDI QIDQ4575666zbMATH OpenOpenAlexFDO

Authors Sunil Arya, David M. Mount

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974331.ch85

zbMATH Keywords

approximation algorithmsEuclidean minimum spanning treeswell-separated pair decompositions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 2079416
• Minimum Spanning Trees in k-Dimensional Space
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• scientific article; zbMATH DE number 437554

Cited in

(11)

• scientific article; zbMATH DE number 2079416 (Why is no real title available?)
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• Parallel algorithms for geometric graph problems
• Approximate geometric MST range queries
• Computing hierarchies of clusters from the Euclidean minimum spanning tree in linear time
• Euclidean minimum spanning trees with independent and dependent geometric uncertainties
• Fast geometric approximation techniques and geometric embedding problems
• Better \(\varepsilon\)-dependencies for offline approximate nearest neighbor search, Euclidean minimum spanning trees, and \(\varepsilon\)-kernels
• On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
• Testing Euclidean minimum spanning trees in the plane
• Approximating \(k\)-hop minimum spanning trees in Euclidean metrics

This page was built for publication: A fast and simple algorithm for computing approximate Euclidean minimum spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575666)