Reut Levi

activity

20132026

most citedA Local Algorithm for Constructing Spanners in Minor-Free Graphs

5 citations · 16 across the 11 of their papers we have counts for

collaborators

Showing 2021Show all

3 papers · 1 filter

cs.DS2021

Testing Triangle Freeness in the General Model in Graphs with Arboricity $O (n)$

Reut Levi

We study the problem of testing triangle freeness in the general graph model. This problem was first studied in the general graph model by Alon et al. (SIAM J. Discret. Math. 2008)…

cs.DS2021

Improved Local Computation Algorithms for Constructing Spanners

Rubi Arviv, Lily Chung, Reut Levi +1

A spanner of a graph is a subgraph that preserves lengths of shortest paths up to a multiplicative distortion. For every $k$ , a spanner with size $O (n^{1 + 1/ k})$ and stretch $(2k+1)…

cs.DS2021

Testing Hamiltonicity (and other problems) in Minor-Free Graphs

Reut Levi, Nadav Shoshan

In this paper we provide sub-linear algorithms for several fundamental problems in the setting in which the input graph excludes a fixed minor, i.e., is a minor-free graph. In part…

Testing Triangle Freeness in the General Model in Graphs with Arboricity O(n​)

Improved Local Computation Algorithms for Constructing Spanners

Testing Hamiltonicity (and other problems) in Minor-Free Graphs

Testing Triangle Freeness in the General Model in Graphs with Arboricity $O (n)$