5 citations · 16 across the 11 of their papers we have counts for
Showing 2017 · cs.DSShow all
3 papers · 2 filters
cs.DS2017★ 3 cited
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…
cs.DS2017
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,…
cs.DS2017★ 2 cited
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…