Gramoz Goranci

collaborators

2 papers

cs.DS2016

Vertex Sparsification in Trees

Gramoz Goranci, Harald Raecke

Given an unweighted tree $T = (V, E)$ with terminals $K \subset V$ , we show how to obtain a $2$ -quality vertex flow and cut sparsifier $H$ with $V_{H} = K$ . We prove that our result is…

cs.DS2016

Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time

Gramoz Goranci, Monika Henzinger, Mikkel Thorup

We present a deterministic incremental algorithm for \textit{exactly} maintaining the size of a minimum cut with $O (1)$ amortized time per edge insertion and $O (1)$ que…