research
∙
07/14/2023
Approximating Edit Distance in the Fully Dynamic Model
The edit distance is a fundamental measure of sequence similarity, defin...
share
research
∙
03/31/2022
Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary
We study reachability and shortest paths problems in dynamic directed gr...
research
∙
11/03/2021
The Parameterized Complexity of the Survivable Network Design Problem
For the well-known Survivable Network Design Problem (SNDP) we are given...
research
∙
09/04/2021
Dynamic Meta-theorems for Distance and Matching
Reachability, distance, and matching are some of the most fundamental gr...
research
∙
08/09/2021
Improved Feature Importance Computations for Tree Models: Shapley vs. Banzhaf
Shapley values are one of the main tools used to explain predictions of ...
research
∙
03/25/2021
Reachability and Matching in Single Crossing Minor Free Graphs
We construct in Logspace non-zero circulations for H-minor free graphs w...
research
∙
03/05/2021
Decomposable Submodular Function Minimization via Maximum Flow
This paper bridges discrete and continuous optimization approaches for d...
research
∙
04/27/2020
Dynamic complexity of Reachability: How many changes can we handle?
In 2015, it was shown that reachability for arbitrary directed graphs ca...
research
∙
06/19/2019
Space Efficient Algorithms for Breadth-Depth Search
Continuing the recent trend, in this article we design several space-eff...
research
∙
04/23/2018
Reachability and Distances under Multiple Changes
Recently it was shown that the transitive closure of a directed graph ca...
research
∙
02/05/2018
Shortest k-Disjoint Paths via Determinants
The well-known k-disjoint path problem (k-DPP) asks for pairwise vertex-...
research
∙
11/27/2017
Frameworks for Designing In-place Graph Algorithms
Read-only memory model is a classical model of computation to study time...
research
∙
12/16/2015