The Library
Testing Euclidean minimum spanning trees in the plane
Tools
Tools
Tools
Czumaj, Artur and Sohler, Christian. (2008) Testing Euclidean minimum spanning trees in the plane. ACM Transactions on Algorithms, Volume 4 (Number 3). p. 31. Article Number 31. ISSN 1549-6325
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
a31-czumaj.pdf - Published Version Restricted to Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (228Kb) |
Official URL: http://dx.doi.org/10.1145/1367064.1367071
Abstract
Given a Euclidean graph G over a set P of n points in the plane, we are interested in verifying whether G is a Euclidean minimum spanning tree (EMST) of P or G differs from it in more than epsilon n edges. We assume that G is given in adjacency list representation and the point/vertex set P is given in an array. We present a property testing algorithm that accepts graph G if it is an EMST of P and that rejects with probability at least 2/3 if G differs from every EMST of P in more than epsilon n edges. Our algorithm runs in O(root n/epsilon . log(2)(n/epsilon)) time and has a query complexity of O(root n/epsilon . log(n/epsilon)).
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||||||
| Divisions: | Faculty of Science > Computer Science | ||||||||
| Library of Congress Subject Headings (LCSH): | Euclidean algorithm, Spanning trees (Graph theory) | ||||||||
| Journal or Publication Title: | ACM Transactions on Algorithms | ||||||||
| Publisher: | Association for Computing Machinery, Inc. | ||||||||
| ISSN: | 1549-6325 | ||||||||
| Official Date: | June 2008 | ||||||||
| Dates: |
|
||||||||
| Volume: | Volume 4 | ||||||||
| Number: | Number 3 | ||||||||
| Number of Pages: | 23 | ||||||||
| Page Range: | p. 31 | ||||||||
| Article Number: | Article Number 31 | ||||||||
| Identification Number: | 10.1145/1367064.1367071 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Funder: | National Science Foundation (U.S.) (NSF), Deutsche Forschungsgemeinschaft (DFG), University of Warwick, Engineering and Physical Sciences Research Council (EPSRC) | ||||||||
| Grant number: | ITR-CCR-0313219 (NSF), CCR-0105701 (NSF), Me872/8-3 (DFG), EP/DO63191/1 (EPSRC) | ||||||||
| URI: | http://wrap.warwick.ac.uk/id/eprint/28017 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
