16 citations · 64 across the 32 of their papers we have counts for
4 papers · 1 filter
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…