5 citations · 16 across the 11 of their papers we have counts for
4 papers · 1 filter
A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error
Hendrik Fichtenberger, Reut Levi, Yadu Vasudev +1
We consider one-sided error property testing of -minor freeness in bounded-degree graphs for any finite family of graphs that contains a minor of $K_{2,k…
Testing bounded arboricity
Talya Eden, Reut Levi, Dana Ron
In this paper we consider the problem of testing whether a graph has bounded arboricity. The family of graphs with bounded arboricity includes, among others, bounded-degree graphs,…
Faster and Simpler Distributed Algorithms for Testing and Correcting Graph Properties in the CONGEST-Model
Guy Even, Reut Levi, Moti Medina
In this paper we present distributed testing algorithms of graph properties in the CONGEST-model [Censor-Hillel et al. 2016]. We present one-sided error testing algorithms in the g…
A Local Algorithm for the Sparse Spanning Graph Problem
Christoph Lenzen, Reut Levi
Constructing a sparse spanning subgraph is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide…