testing of large graphs

Noga Alon, Eldar Fischer, Michael Krivelevich, Márió Szegedy

Type: Article

Publication Date: 2000-01-01

Citations: 23

Similar Works

Action	Title	Year	Authors
+	Efficient testing of large graphs	2003	Noga Alon Michael Krivelevich E. Fischer Márió Szegedy
+	Testing graphs for colorable properties	2001	Eldar Fischer
+	Efficient Testing of Large Graphs	2000	Noga Alon Eldar Fischer Michael Krivelevich Márió Szegedy
+	Efficient Testing of Hypergraphs	2002	Yoshiharu Kohayakawa Brendan Nagle Vojtěch Rödl
+	A combinatorial characterization of the testable graph properties	2006	Noga Alon Eldar Fischer Ilan Newman A. Shapira
+ PDF Chat	Every monotone graph property is testable	2005	Noga Alon A. Shapira
+	Fast property testing and metrics for permutations	2016	Jacob Fox Fan Wei
+ PDF Chat	Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability	2015	Eldar Fischer Oded Lachish Yadu Vasudev
+	Regular partitions of hypergraphs and property testing	2010	Mathias Schacht
+	Property testing and parameter estimation	2020	Henrique Stagni
+	On Testability of First-Order Properties in Bounded-Degree Graphs	2020	Isolde Adler Noleen Köhler Pan Peng
+	Property testing in bounded degree graphs	1997	Oded Goldreich Dana Ron
+	On testable properties in bounded degree graphs	2007	Artur Czumaj Christian Sohler
+	Testing of graph properties	2021	Ilan Newman
+ PDF Chat	Fast Property Testing and Metrics for Permutations	2018	Jacob Fox Fan Wei
+	Homomorphisms in Graph Property Testing - A Survey	2005	A. Shapira Noga Alon
+ PDF Chat	Testing properties of graphs and functions	2010	László Lovász Balázs Szegedy
+	Property testing in hypergraphs and the removal lemma	2007	V. Rödl Mathias Schacht
+ PDF Chat	Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing	2022	Oded Goldreich Avi Wigderson
+	On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	2023	Isolde Adler Noleen Köhler Pan Peng

Works That Cite This (13)

Action	Title	Year	Authors
+	Testing whether a digraph contains H-free k-induced subgraphs	2008	Hong-Yiu Lin Yuh‐Dauh Lyuu Tak-Man Ma Yen‐Wu Ti
+	Extremal results in sparse pseudorandom graphs	2014	David Conlon Jacob Fox Yufei Zhao
+	Property Testing in Hypergraphs and the Removal Lemma (Extended Abstract)	2007	Mathias Schacht
+	Endre Szemerédi, Premi Abel 2012	2013	Gábor Lugosi Oriol Serra
+ PDF Chat	Regular Partitions of Hypergraphs: Regularity Lemmas	2007	Vojtěch Rödl Mathias Schacht
+	The edit distance function for graphs: an exploration of the case of forbidden induced K<sub>2,t</sub> and other questions	2012	Tracy McKay
+	Sparse Combinatorial Structures: Classification and Applications	2011	Jaroslav Nešetřil Patrice Ossona de Mendez
+ PDF Chat	Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐Universal	2014	Nati Linial Avraham Morgenstern
+	Property testing and parameter testing for permutations	2010	Carlos Hoppen Yoshiharu Kohayakawa Carlos Gustavo Moreira Rudini Sampaio
+	Regularity Lemmas for Graphs	2010	Vojtěch Rödl Mathias Schacht

Works Cited by This (8)

Action	Title	Year	Authors
+	Extremal Graph Theory	1978	Béla Bollobás
+	Szemeredi''s Regularity Lemma and its applications in graph theory	1995	János Komlós Miklós Simonovits
+ PDF Chat	Extremal Graphs without Large Forbidden Subgraphs	1978	B Bollobás P. Erdős Miklós Simonovits Endre Szemerédi
+	Lower bounds of tower type for Szemerédi's uniformity lemma	1997	W. T. Gowers
+	On graphs with small subgraphs of large chromatic number	1985	V. Rödl Richard A. Duke
+	On Sets of Integers Which Contain No Three Terms in Arithmetical Progression	1946	Felix Behrend
+ PDF Chat	The Algorithmic Aspects of the Regularity Lemma	1994	Noga Alon Richard A. Duke Hanno Lefmann V. Rödl Raphael Yuster
+	REGULAR PARTITIONS OF GRAPHS	1975	Endre Szemerédi