Every Minor-Closed Property of Sparse Graphs is Testable.

Itaı Benjamini, Oded Schramm, A. Shapira

Type: Article

Publication Date: 2008-01-01

Citations: 1

Locations

Electronic colloquium on computational complexity - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Every minor-closed property of sparse graphs is testable	2008	Itaï Benjamini Oded Schramm A. Shapira
+	Every Minor-Closed Property of Sparse Graphs is Testable	2008	Itaı Benjamini Oded Schramm A. Shapira
+	Minors, connectivity, and diameter in randomly perturbed sparse graphs	2022	Elad Aigner‐Horev Dan Hefetz Michael Krivelevich
+	Testing Hamiltonicity (and other problems) in Minor-Free Graphs	2021	Reut Levi Nadav Shoshan
+	Testing Hamiltonicity (and other problems) in Minor-Free Graphs	2021	Reut Levi Nadav Shoshan
+	Random walks and forbidden minors II: A $\text{poly}(d\varepsilon^{-1})$-query tester for minor-closed properties of bounded-degree graphs	2019	Akash Kumar C. Seshadhri Andrew Stolman
+	Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	2022	Akash Kumar C. Seshadhri Andrew Stolman
+	Finding forbidden minors in sublinear time: a $n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs	2018	Akash Kumar C. Seshadhri Andrew Stolman
+	Finding forbidden minors in sublinear time: a $n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs	2018	Akash Kumar C. Seshadhri Andrew Stolman
+	Maximum degree in minor-closed classes of graphs	2013	Omer Giménez Dieter Mitsche Marc Noy
+	Maximum degree in minor-closed classes of graphs	2013	Omer Giménez Dieter Mitsche Marc Noy
+	On random graphs from a minor-closed class	2016	Colin McDiarmid
+	Random walks and forbidden minors III: poly(d/ε)-time partition oracles for minor-free graph classes	2021	Akash Kumar C. Seshadhri Andrew Stolman
+	Random walks and forbidden minors III: poly(d/{\epsilon})-time partition oracles for minor-free graph classes	2021	Akash Kumar C. Seshadhri Andrew Stolman
+ PDF Chat	Asymptotic properties of some minor-closed classes of graphs (conference version)	2013	Mireille Bousquet‐Mélou Kerstin Weller
+	None	2016
+ PDF Chat	Planar graphs: Random walks and bipartiteness testing	2019	Artur Czumaj Morteza Monemizadeh Krzysztof Onak Christian Sohler
+ PDF Chat	Planar Graphs: Random Walks and Bipartiteness Testing	2011	Artur Czumaj Morteza Monemizadeh Krzysztof Onak Christian Sohler
+	Graphs without Large Complete Minors are Quasi-Random	2002	Joseph Samuel Myers
+	Quantitative Small Subgraph Conditioning	2013	Tobias Johnson Elliot Paquette

Works That Cite This (1)

Action	Title	Year	Authors
+ PDF Chat	A Lower Bound on Cycle-Finding in Sparse Digraphs	2019	Xi Chen Tim Randolph Rocco A. Servedio Timothy Sun

Works Cited by This (14)

Action	Title	Year	Authors
+	Sublinear-time algorithms	2006	Artur Czumaj Christian Sohler
+	On Testing Expansion in Bounded-Degree Graphs	2000	Oded Goldreich Dana Ron
+	The combinatorial cost	2006	Gábor Elek
+	On testable properties in bounded degree graphs	2007	Artur Czumaj Christian Sohler
+	Über eine Eigenschaft der ebenen Komplexe	1937	Klaus W. Wagner
+	None	2010	Christian Borgs Jennifer Chayes Ayalvadi Ganesh Amin Saberi
+	Testing the diameter of graphs	2002	Michal Parnas Dana Ron
+	REGULAR PARTITIONS OF GRAPHS	1975	Endre Szemerédi
+ PDF Chat	Graph limits and parameter testing	2006	Christian Borgs Jennifer Chayes László Lovász Vera T. Sós Balázs Szegedy K. Vesztergombi
+ PDF Chat	Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring	2005	Erik D. Demaine Mohammad Taghi Hajiaghayi Ken‐ichi Kawarabayashi