18 citations · 44 across the 10 of their papers we have counts for
20 papers
Dynamic Maximal Independent Set using Predictions
Shahbaz Khan, Anshul Kumar
We present the first dynamic maximal independent set (MIS) of a graph with vertices and up to edges under edge updates in the prediction model, where a predicted update seq…
Dynamic Breadth First Search with Predictions
Shahbaz Khan, Shubham Kumar Verma, Utkarsh Lohiya
Given a graph having vertices and edges, we maintain its Breadth-First Search (BFS) tree from source under an online sequence of edge updates in the predic…
Evaluating Optimal Safe Flows Decomposition for RNA Assembly
Bashar Ahmed, Siddharth Singh Rana, Ujjwal +1
In Bioinformatics, the applications of flow decomposition in directed acyclic graphs are highlighted in RNA Assembly problem. However, it admits multiple solutions where exactly on…
Engineering Semi-streaming DFS algorithms
Kancharla Nikhilesh Bhagavan, Macharla Sri Vardhan, Madamanchi Ashok Chowdary +1
Depth first search is a fundamental graph problem having a wide range of applications. For a graph having vertices and edges, the DFS tree can be computed in $O(m…
Practical algorithms for Hierarchical overlap graphs
Saumya Talera, Parth Bansal, Shabnam Khan +1
Genome assembly is a prominent problem studied in bioinformatics, which computes the source string using a set of its overlapping substrings. Classically, genome assembly uses asse…
Cut paths and their remainder structure, with applications
Massimo Cairo, Shahbaz Khan, Romeo Rizzi +3
In a strongly connected graph , a cut arc (also called strong bridge) is an arc whose removal makes the graph no longer strongly connected. Equivalently, there…
Width Helps and Hinders Splitting Flows
Manuel Cáceres, Massimo Cairo, Andreas Grigorjew +5
Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulation on a directed graph into weighted source-to-sink p…
Safety and Completeness in Flow Decompositions for RNA Assembly
Shahbaz Khan, Milla Kortelainen, Manuel Cáceres +2
Decomposing a network flow into weighted paths has numerous applications. Some applications require any decomposition that is optimal w.r.t. some property such as number of paths,…
Optimizing Safe Flow Decompositions in DAGs
Shahbaz Khan, Alexandru I. Tomescu
Network flow is one of the most studied combinatorial optimization problems having innumerable applications. Any flow on a directed acyclic graph having vertices and ed…
Optimal Construction of Hierarchical Overlap Graphs
Shahbaz Khan
Genome assembly is a fundamental problem in Bioinformatics, where for a given set of overlapping substrings of a genome, the aim is to reconstruct the source genome. The classical…
The Hydrostructure: a Universal Framework for Safe and Complete Algorithms for Genome Assembly
Massimo Cairo, Shahbaz Khan, Romeo Rizzi +3
Genome assembly is a fundamental problem in Bioinformatics, requiring to reconstruct a source genome from an assembly graph built from a set of reads (short strings sequenced from…
Safety in - Paths, Trails and Walks
Massimo Cairo, Shahbaz Khan, Romeo Rizzi +2
Given a directed graph and a pair of nodes and , an \emph{- bridge} of is an edge whose removal breaks all - paths of (and thus appears in all -$t…
Computing all - bridges and articulation points simplified
Massimo Cairo, Shahbaz Khan, Romeo Rizzi +3
Given a directed graph and a pair of nodes and , an - bridge of is an edge whose removal breaks all - paths of . Similarly, an - articulation po…
Dynamic Matching Algorithms in Practice
Monika Henzinger, Shahbaz Khan, Richard Paul +1
In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very…
Depth First Search in the Semi-streaming Model
Shahbaz Khan, Shashank K. Mehta
Depth first search (DFS) tree is a fundamental data structure for solving various graph problems. The classical DFS algorithm requires time for a graph having vertices…
Simple dynamic algorithms for Maximal Independent Set and other problems
Manoj Gupta, Shahbaz Khan
Most graphs in real life keep changing with time. These changes can be in the form of insertion or deletion of edges or vertices. Such rapidly changing graphs motivate us to study…
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 time for a gi…
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 with vertices and edges can be built in time.…
Multiple Source Dual Fault Tolerant BFS Trees
Manoj Gupta, Shahbaz Khan
Let be a graph with vertices and edges, with a designated set of sources . The fault tolerant subgraph for any graph problem maintains a sparse…
Dynamic DFS Tree in Undirected Graphs: breaking the barrier
Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary +1
Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It is well known that it takes time to build a DFS tree for a given u…