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 2026Show all

2 papers · 1 filter

cs.DS2026

Dynamic Maximal Independent Set using Predictions

Shahbaz Khan, Anshul Kumar

We present the first dynamic maximal independent set (MIS) of a graph with $n$ vertices and up to $m$ edges under edge updates in the prediction model, where a predicted update seq…

cs.DS2026

Dynamic Breadth First Search with Predictions

Shahbaz Khan, Shubham Kumar Verma, Utkarsh Lohiya

Given a graph $G (V, E)$ having $n$ vertices and $m$ edges, we maintain its Breadth-First Search (BFS) tree from source $s$ under an online sequence of $u$ edge updates in the predic…