Sayan Bhattacharya

activity

20092026

most citedOn Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids

16 citations · 64 across the 32 of their papers we have counts for

collaborators

Showing 2018Show all

2 papers · 1 filter

cs.DS2018★ 3 cited

An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs

Sayan Bhattacharya, Janardhan Kulkarni

We consider the problem of incremental cycle detection and topological ordering in a directed graph $G = (V, E)$ with $∣ V ∣ = n$ nodes. In this setting, initially the edge-set $E$ o…

cs.DS2018

Deterministically Maintaining a $(2 + ε)$ -Approximate Minimum Vertex Cover in $O (1/ ε^{2})$ Amortized Update Time

Sayan Bhattacharya, Janardhan Kulkarni

We consider the problem of maintaining an (approximately) minimum vertex cover in an $n$ -node graph $G = (V, E)$ that is getting updated dynamically via a sequence of edge insertio…

An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs

Deterministically Maintaining a (2+ε)-Approximate Minimum Vertex Cover in O(1/ε2) Amortized Update Time

Deterministically Maintaining a $(2 + ε)$ -Approximate Minimum Vertex Cover in $O (1/ ε^{2})$ Amortized Update Time