2 citations · 2 across the 3 of their papers we have counts for
3 papers
Steiner Transitive-Closure Spanners of d-Dimensional Posets
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu +3
Given a directed graph G and an integer k >= 1, a k-transitive-closure-spanner (k-TCspanner) of G is a directed graph H that has (1) the same transitive-closure as G and (2) diamet…
Transitive-Closure Spanners
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung +2
Given a directed graph G = (V,E) and an integer k>=1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, E_H) that has (1) the same transitive-closure a…
Sublinear Algorithms for Approximating String Compressibility
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld +1
We raise the question of approximating the compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popul…