Testing Bounded Arboricity

DOI10.1145/3381418zbMath1403.68160arXiv1707.04864MaRDI QIDQ4608029

Dana Ron, Reut Levi, Talya Eden

Publication date: 15 March 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.04864

zbMATH Keywords

property testing; graph arboricity; graph degeneracy; tolerant testing

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

68W20: Randomized algorithms