14 citations · 29 across the 7 of their papers we have counts for
13 papers
Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut
Surender Baswana, Koustav Bhanja, Anupam Roy
We study (s,t)-cuts of second minimum capacity and present the following algorithmic and graph-theoretic results. 1. Vazirani and Yannakakis [ICALP 1992] designed the first algorit…
The connectivity carcass of a vertex subset in a graph: both odd and even case
Surender Baswana, Abhyuday Pandey
Let be an undirected unweighted multi-graph and be a subset of vertices. A set of edges with the least cardinality whose removal disconnects , that is,…
Vital Edges for (s,t)-mincut: Efficient Algorithms, Compact Structures, and Optimal Sensitivity Oracle
Surender Baswana, Koustav Bhanja
Let G be a directed weighted graph (DiGraph) on n vertices and m edges with source s and sink t. An edge in G is vital if its removal reduces the capacity of (s,t)-mincut. Since th…
Sensitivity Oracles for All-Pairs Mincuts
Surender Baswana, Abhyuday Pandey
Let be an undirected unweighted graph on vertices and edges. We address the problem of sensitivity oracle for all-pairs mincuts in defined as follows. Build a…
Joint Seat Allocation 2018: An algorithmic perspective
Surender Baswana, Partha Pratim Chakrabarti, Yashodhan Kanoria +2
Until 2014, admissions to the Indian Institutes of Technology (IITs) were conducted under one umbrella, whereas the admissions to the non-IIT Centrally Funded Government Institutes…
Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient
Surender Baswana, Shiv Kumar Gupta, Ayush Tulsyan
We present an algorithm for a fault tolerant Depth First Search (DFS) Tree in an undirected graph. This algorithm is drastically simpler than the current state-of-the-art algorithm…