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. doi:10.1145/1367064.1367071
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
a31-czumaj.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. 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 | ||||||||
| DOI: | 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) |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
