The Library
Testing Euclidean minimum spanning trees in the plane
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 ISSN 1549-6325.
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, Engineering and Medicine > 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 | ||||||||
Date of first compliant deposit: | 13 December 2015 | ||||||||
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 |