Shahbaz Khan

activity

20152026

most citedSimple dynamic algorithms for Maximal Independent Set and other problems

18 citations · 44 across the 10 of their papers we have counts for

collaborators

Showing 2017Show all

3 papers · 1 filter

cs.DS2017★ 5 cited

Near Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs

Shahbaz Khan

Depth first search (DFS) tree is a fundamental data structure for solving graph problems. The classical algorithm [SiComp74] for building a DFS tree requires $O (m + n)$ time for a gi…

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.DS2017★ 4 cited

Multiple Source Dual Fault Tolerant BFS Trees

Manoj Gupta, Shahbaz Khan

Let $G = (V, E)$ be a graph with $n$ vertices and $m$ edges, with a designated set of $σ$ sources $S \subseteq V$ . The fault tolerant subgraph for any graph problem maintains a sparse…