4 papers · 1 filter
Dynamic Hierarchical -Tree Decomposition and Its Applications
Gramoz Goranci, Monika Henzinger, Peter Kiss +2
We develop a new algorithmic framework for designing approximation algorithms for cut-based optimization problems on capacitated undirected graphs that undergo edge insertions and…
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 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…
Fully Dynamic Spectral Sparsification of Hypergraphs
Gramoz Goranci, Ali Momeni
Spectral hypergraph sparsification, a natural generalization of the well-studied spectral sparsification notion on graphs, has been the subject of intensive research in recent year…