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

DOI10.1137/1.9781611974331.CH85zbMATH Open1410.68393OpenAlexW4231737678MaRDI QIDQ4575666FDOQ4575666

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

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
• Time-space trade-offs for computing Euclidean minimum spanning trees

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)

Cited In (7)

• Euclidean minimum spanning trees with independent and dependent geometric uncertainties
• Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
• Fast geometric approximation techniques and geometric embedding problems
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• Time-space trade-offs for computing Euclidean minimum spanning trees
• Title not available (Why is that?)
• Testing Euclidean minimum spanning trees in the plane

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)