scientific article; zbMATH DE number 7559080

DOI10.4230/LIPIcs.ITCS.2019.37zbMath1495.68177MaRDI QIDQ5090414

Oded Goldreich, Dana Ron

Publication date: 18 July 2022

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

graph propertiesproperty testing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cites Work

• On the benefits of adaptivity in property testing of dense graphs
• Property testing. Current research and surveys
• Every minor-closed property of sparse graphs is testable
• A sublinear bipartiteness tester for bounded degree graphs
• Every Property of Hyperfinite Graphs Is Testable
• On Proximity-Oblivious Testing
• Parameter testing in bounded degree graphs of subexponential growth
• An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
• Property testing and its connection to learning and approximation
• On the query complexity of testing orientations for being Eulerian
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• Embedding Outerplanar Graphs in Small Books
• A Separator Theorem for Planar Graphs
• Testing the diameter of graphs
• Estimating the Unseen
• Tight Bounds for Testing Bipartiteness in General Graphs
• On the asymmetry of random regular graphs and random graphs
• Property Testing of Massively Parametrized Problems – A Survey
• A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
• Local Graph Partitions for Approximation and Testing
• lgorithmic and Analysis Techniques in Property Testing
• Introduction to Property Testing
• Planar Graphs: Random Walks and Bipartiteness Testing
• Some 3CNF Properties Are Hard to Test
• Asymmetric graphs
• Computational Complexity
• Property testing in bounded degree graphs

This page was built for publication: