16 citations · 64 across the 32 of their papers we have counts for
37 papers
Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition
Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak +1
We study the low-degree Steiner forest decomposition. Given a graph and a terminal set , the standard decomposition returns a set of size at…
Minimum Degree Spanning Tree: -Approximation in Near-Linear Time
Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak +1
The minimum degree spanning tree problem is a classic NP-hard problem whose optimal approximation guarantee was established since the early 1990s: Fürer and Raghavachari [FR92] gav…
The unbreakable quasi-graphic matroids
Sayantani Bhattacharya, John David Clifton, Zach Walsh
A matroid M is unbreakable if it is connected and M/F is connected for every flat F of M . Oxley and Pfeil characterized the unbreakable graphic matroids, and Fife, Mayhew, Oxley,…
Additive One Approximation for Minimum Degree Spanning Tree: Breaking the Time Barrier
Sayan Bhattacharya, Ermiya Farokhnejad, Haoze Wang
We consider the ``minimum degree spanning tree'' problem. As input, we receive an undirected, connected graph with nodes and edges, and our task is to find a spa…
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer +2
We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, bas…
Deterministic Dynamic Maximal Matching in Sublinear Update Time
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss +1
We give a fully dynamic deterministic algorithm for maintaining a maximal matching of an -vertex graph in amortized update time. This breaks the long-standi…