2 citations · 3 across the 4 of their papers we have counts for
3 papers · 1 filter
Improved Approximation for the Directed Spanner Problem
Arnab Bhattacharyya, Konstantin Makarychev
We prove that the size of the sparsest directed k-spanner of a graph can be approximated in polynomial time to within a factor of , for all k >= 3. This improv…
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…
A Unified Framework for Testing Linear-Invariant Properties
Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira
The study of the interplay between the testability of properties of Boolean functions and the invariances acting on their domain which preserve the property was initiated by Kaufma…