D. Ron

activity

20072023

most citedA Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor

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

collaborators

Showing 2018Show all

2 papers · 1 filter

cs.DS2018

Faster sublinear approximations of $k$ -cliques for low arboricity graphs

Talya Eden, Dana Ron, C. Seshadhri

Given query access to an undirected graph $G$ , we consider the problem of computing a $(1 \pm ε)$ -approximation of the number of $k$ -cliques in $G$ . The standard query model for gene…

cs.DC2018

Property Testing of Planarity in the CONGEST model

Reut Levi, Moti Medina, Dana Ron

We give a distributed algorithm in the {\sf CONGEST} model for property testing of planarity with one-sided error in general (unbounded-degree) graphs. Following Censor-Hillel et a…

Faster sublinear approximations of k-cliques for low arboricity graphs

Property Testing of Planarity in the CONGEST model

Faster sublinear approximations of $k$ -cliques for low arboricity graphs