20 citations · 71 across the 26 of their papers we have counts for
34 papers
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…
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 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…
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…
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 insertions…
Fully Dynamic Algorithms for Euclidean Steiner Tree
T-H. Hubert Chan, Gramoz Goranci, Shaofeng H. -C. Jiang +2
The Euclidean Steiner tree problem asks to find a min-cost metric graph that connects a given set of \emph{terminal} points in , possibly using points not in …
Fast Algorithms for Separable Linear Programs
Sally Dong, Gramoz Goranci, Lawrence Li +2
In numerical linear algebra, considerable effort has been devoted to obtaining faster algorithms for linear systems whose underlying matrices exhibit structural properties. A promi…
Dynamic algorithms for k-center on graphs
Emilio Cruciani, Sebastian Forster, Gramoz Goranci +2
In this paper we give the first efficient algorithms for the -center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into…
Bootstrapping Dynamic Distance Oracles
Sebastian Forster, Gramoz Goranci, Yasamin Nazari +1
Designing approximate all-pairs distance oracles in the fully dynamic setting is one of the central problems in dynamic graph algorithms. Despite extensive research on this topic,…
Electrical Flows for Polylogarithmic Competitive Oblivious Routing
Gramoz Goranci, Monika Henzinger, Harald Räcke +2
Oblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polyl…
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Gramoz Goranci, Monika Henzinger, Danupon Nanongkai +3
Given a simple -vertex, -edge graph undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of $G…
Incremental Approximate Maximum Flow in update time
Gramoz Goranci, Monika Henzinger
We show an -approximation algorithm for maintaining maximum - flow under edge insertions in amortized update time for directed, unweighted…
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
Sally Dong, Yu Gao, Gramoz Goranci +4
We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm fo…
Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing
Goran Zuzic, Gramoz Goranci, Mingquan Ye +2
We provide universally-optimal distributed graph algorithms for -approximate shortest path problems including shortest-path-tree and transshipment. The universal o…
Local Algorithms for Estimating Effective Resistance
Pan Peng, Daniel Lopatta, Yuichi Yoshida +1
Effective resistance is an important metric that measures the similarity of two vertices in a graph. It has found applications in graph clustering, recommendation systems and netwo…
Minor Sparsifiers and the Distributed Laplacian Paradigm
Sebastian Forster, Gramoz Goranci, Yang P. Liu +3
We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrice…
Faster Graph Embeddings via Coarsening
Matthew Fahrbach, Gramoz Goranci, Richard Peng +2
Graph embeddings are a ubiquitous tool for machine learning tasks, such as node classification and link prediction, on graph-structured data. However, computing the embeddings for…
Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers
Li Chen, Gramoz Goranci, Monika Henzinger +2
We present a general framework of designing efficient dynamic approximate algorithms for optimization on undirected graphs. In particular, we develop a technique that, given any pr…
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak +1
We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with …
Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications
Sebastian Forster, Gramoz Goranci, Monika Henzinger
We give the first non-trivial fully dynamic probabilistic tree embedding algorithm for weighted graphs undergoing edge insertions and deletions. We obtain a trade-off between amort…
A Tree Structure For Dynamic Facility Location
Gramoz Goranci, Monika Henzinger, Dariusz Leniowski
We study the metric facility location problem with client insertions and deletions. This setting differs from the classic dynamic facility location problem, where the set of client…
Dynamic Graph Algorithms and Graph Sparsification: New Techniques and Connections
Gramoz Goranci
Graphs naturally appear in several real-world contexts including social networks, the web network, and telecommunication networks. While the analysis and the understanding of graph…