Showing math.COShow all
2 papers · 1 filter
math.CO2008
Every Minor-Closed Property of Sparse Graphs is Testable
Itai Benjamini, Oded Schramm, Asaf Shapira
Suppose is a graph with degrees bounded by , and one needs to remove more than of its edges in order to make it planar. We show that in this case the statistics of loca…
math.CO2007
Additive approximation for edge-deletion problems
Noga Alon, Asaf Shapira, Benny Sudakov
A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following edge-deletion problem; given a monotone property P and a g…