Testing Euclidean Spanners

DOI10.1007/978-3-642-16367-8_24MaRDI QIDQ4933382zbMATH OpenOpenAlexFDO

Authors Frank Hellweg, Melanie Schmidt, Christian Sohler

Publication date 12 October 2010

Published in Property Testing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16367-8_24

zbMATH Keywords

geometric propertiessparse graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cites work

• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Algebraic property testing: the role of invariance
• Approximating the Stretch Factor of Euclidean Graphs
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• Dilation-Optimal Edge Deletion in Polygonal Cycles
• Efficient testing of large graphs
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• Every Monotone 3‐Graph Property is Testable
• Finding the best shortcut in a geometric network
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Geometric Spanner Networks
• scientific article; zbMATH DE number 1670655 (Why is no real title available?)
• scientific article; zbMATH DE number 437554 (Why is no real title available?)
• scientific article; zbMATH DE number 5485551 (Why is no real title available?)
• scientific article; zbMATH DE number 4070353 (Why is no real title available?)
• scientific article; zbMATH DE number 1263225 (Why is no real title available?)
• scientific article; zbMATH DE number 1875421 (Why is no real title available?)
• Minimum dilation stars
• Monotonicity testing over general poset domains
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• Sublinear Geometric Algorithms
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• Testing hypergraph colorability
• Testing juntas nearly optimally
• Testing monotonicity
• Testing of Clustering
• Testing the diameter of graphs

Cited in

(4)

• Testing Euclidean Spanners
• Testing Euclidean minimum spanning trees in the plane
• Distribution-sensitive construction of the greedy spanner
• Online Euclidean Spanners

This page was built for publication: Testing Euclidean Spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933382)