We give a deterministic m^1+o(1) time algorithm that computes exact maximum flows and
minimum-cost flows on directed graphs with m edges and polynomially bounded integral …

We present an ̃O(m+n^1.5)-time randomized algorithm for maximum cardinality bipartite
matching and related problems (eg transshipment, negative-weight shortest paths, and …

We give an algorithm for computing exact maximum flows on graphs with edges and integer
capacities in the range in time. We use to suppress logarithmic factors in. For sparse graphs …

Network flow problems form an important and much‐studied family of combinatorial
optimization problems, with a huge array of practical applications. Two network flow …

We present an algorithm which given any m-edge directed graph with positive integer
capacities at most U, vertices a and b, and an approximation parameter ϵ∈(0,1) computes …

Let G=(V, E, w) be a weighted, directed graph subject to a sequence of adversarial edge
deletions. In the decremental single-source reachability problem (SSR), we are given a fixed …

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 n …

We present a randomized algorithm that computes single-source shortest paths (SSSP) in
O\left(m\log^8(n)\logW\right) time when edge weights are integral and can be negative. 1 …

Given an input that undergoes a sequence of updates, a dynamic algorithm maintains a
valid solution to some predefined problem at any point in time; the goal is to design an …

We give a deterministic (global) min-cut algorithm for weighted undirected graphs that runs
in time O (m 1+ ε) plus polylog (n) max-flow computations. Using the current best max-flow …