Estimating the weight of metric minimum spanning trees in sublinear-time
- 13 June 2004
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 175-183
- https://doi.org/10.1145/1007352.1007386
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- A sublinear algorithm for weakly approximating edit distancePublished by Association for Computing Machinery (ACM) ,2003
- Sublinear geometric algorithmsPublished by Association for Computing Machinery (ACM) ,2003
- An optimal minimum spanning tree algorithmJournal of the ACM, 2002
- Approximating the Minimum Spanning Tree Weight in Sublinear TimeLecture Notes in Computer Science, 2001
- A minimum spanning tree algorithm with inverse-Ackermann type complexityJournal of the ACM, 2000
- Sublinear time algorithms for metric space problemsPublished by Association for Computing Machinery (ACM) ,1999
- Property testing and its connection to learning and approximationJournal of the ACM, 1998
- A randomized linear-time algorithm to find minimum spanning treesJournal of the ACM, 1995
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fieldsJournal of the ACM, 1995
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related ProblemsSIAM Journal on Computing, 1982