Testing Euclidean Spanners

DOI10.1007/978-3-642-16367-8_24zbMath1309.68223OpenAlexW2529328061MaRDI QIDQ4933382

Frank Hellweg, Christian Sohler, Melanie Schmidt

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

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

Related Items (1)

Distribution-sensitive construction of the greedy spanner

Cites Work

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

This page was built for publication: Testing Euclidean Spanners