Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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] 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

Request Changes to record.

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:
DateEvent
June 2008Published
October 2007Accepted
December 2004Submitted
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us