We give a randomized algorithm that finds a minimum cut in an undirected weighted m-edge
n-vertex graph G with high probability in O (m log 2 n) time. This is the first improvement to …

We give the first almost-linear time algorithms for several problems in incremental graphs
including cycle detection, strongly connected component maintenance, st shortest path …

We present a general toolbox, based on new vertex sparsifiers, for designing data structures
to maintain shortest paths in graphs undergoing edge insertions and/or deletions. In …

Maximum bipartite matching (MBM) is a fundamental problem in combinatorial optimization
with a long and rich history. A classic result of Hopcroft and Karp (1973) provides an $ O …

We provide an algorithm which, with high probability, maintains a (1—ɛ)-approximate
maximum flow on an undirected graph undergoing m-edge additions in amortized mo (1) ɛ …

In this work, we present the first algorithm to compute expander decompositions in an $ m $-
edge directed graph with near-optimal time $\tilde {O}(m) $. Further, our algorithm can …

We provide an algorithm that maintains, against an adaptive adversary, a $(1-\varepsilon) $-
approximate maximum matching in $ n $-node $ m $-edge general (not necessarily …

Maximum bipartite matching (MBM) is a fundamental problem in combinatorial optimization
with a long and rich history. A classic result of Hopcroft and Karp (1973) provides an O (m√ …

An $ n $-vertex $ m $-edge graph is\emph {$ k $-vertex connected} if it cannot be
disconnected by deleting less than $ k $ vertices. After more than half a century of intensive …

In this paper, we consider the problem of maintaining a $(1-\varepsilon) $-approximate
maximum weight matching in a dynamic graph $ G $, while the adversary makes changes to …