Lower bounds for testing Euclidean minimum spanning trees

DOI10.1016/j.ipl.2006.12.011zbMath1189.90129OpenAlexW2116207970MaRDI QIDQ846011

Oren Ben-Zwi, Ilan Newman, Oded Lachish

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.12.011

zbMATH Keywords

graph algorithmscomputational geometryrandomized algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing Euclidean minimum spanning trees in the plane
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower bounds for testing Euclidean minimum spanning trees