Czumaj, Artur and Sohler, Christian. (2008) Testing Euclidean minimum spanning trees in the plane. ACM Transactions on Algorithms , Vol.4 (No.3). p. 31. ISSN 1549-6325

Full text not available from this repository.

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
Date:	June 2008
Volume:	Vol.4
Number:	No.3
Number of Pages:	23
Page Range:	p. 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

Request changes to a record

Actions (login required)

View Item