7 papers
Incremental Approximate Maximum Flow via Residual Graph Sparsification
Gramoz Goranci, Monika Henzinger, Harald Räcke +1
We give an algorithm that, with high probability, maintains a -approximate - maximum flow in undirected, uncapacitated -vertex graphs undergoing edge insertion…
Tree Embedding in High Dimensions: Dynamic and Massively Parallel
Gramoz Goranci, Shaofeng H. -C. Jiang, Peter Kiss +3
Tree embedding has been a fundamental method in algorithm design with wide applications. We focus on the efficiency of building tree embedding in various computational settings und…
Fully Dynamic Spectral Sparsification for Directed Hypergraphs
Sebastian Forster, Gramoz Goranci, Ali Momeni
There has been a surge of interest in spectral hypergraph sparsification, a natural generalization of spectral sparsification for graphs. In this paper, we present a simple fully d…
Fully Dynamic Algorithms for Chamfer Distance
Gramoz Goranci, Shaofeng Jiang, Peter Kiss +2
We study the problem of computing Chamfer distance in the fully dynamic setting, where two set of points , each of size up to , dynamically evolve t…
Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
Gramoz Goranci, Peter Kiss, Neel Patel +3
We consider the Euclidean bi-chromatic matching problem in the dynamic setting, where the goal is to efficiently process point insertions and deletions while maintaining a high-qua…
Fully Dynamic Algorithms for Transitive Reduction
Gramoz Goranci, Adam Karczmarz, Ali Momeni +1
Given a directed graph , a transitive reduction of (first studied by Aho, Garey, Ullman [SICOMP `72]) is a minimal subgraph of that preserves the reachability rela…