Surender Baswana

activity

20062020

most citedFaster Streaming algorithms for graph spanners

6 citations · 10 across the 2 of their papers we have counts for

collaborators

Showing cs.DSShow all

5 papers · 1 filter

cs.DS2020

Sensitivity Oracles for All-Pairs Mincuts

Surender Baswana, Abhyuday Pandey

Let $G = (V, E)$ be an undirected unweighted graph on $n$ vertices and $m$ edges. We address the problem of sensitivity oracle for all-pairs mincuts in $G$ defined as follows. Build a…

cs.DS2018

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…

cs.DS2017

Incremental DFS algorithms: a theoretical and experimental study

Surender Baswana, Ayush Goel, Shahbaz Khan

Depth First Search (DFS) tree is a fundamental data structure for solving graph problems. The DFS tree of a graph $G$ with $n$ vertices and $m$ edges can be built in $O (m + n)$ time.…

cs.DS2012★ 4 cited

Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs

Abhash Anand, Surender Baswana, Manoj Gupta +1

We present a fully dynamic algorithm for maintaining approximate maximum weight matching in general weighted graphs. The algorithm maintains a matching $M$ whose weight is a…

cs.DS2006★ 6 cited

Faster Streaming algorithms for graph spanners

Surender Baswana

Given an undirected graph $G = (V, E)$ on $n$ vertices, $m$ edges, and an integer $t \geq 1$ , a subgraph $(V, E_{S})$ , $E_{S} \subseteq E$ is called a $t$ -spanner if for any pair of vertices…