Misc.

[Chekuri, Quanrud, ICALP'21] Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity Problems

[Li, Nanongkai, Panigrahi, Saranurak] Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time

[Ghaffari, Kuhn, Su, PODC'17] Distributed MST and Routing in Almost Mixing Time

String Sketching

Improved sketching of hamming distance with error correcting [Porat, Lipsky, CPM'07]

Connectivity

Vertex Sampling and Vertex Connectivity

[Censor-Hillel, Ghaffari, Kuhn, SODA'14] A New Perspective on Vertex Connectivity, sampling with probability $p$ leads to $\Omega(kp^2/\log^3 n)$ connected.

[ Censor-Hillel, Ghaffari, Giakkoupis, Haeupler, Kuhn, SODA'15] Tight Bounds on Vertex Connectivity Under Vertex Sampling, improved to $\Omega(kp^2)$, which is optimal.

Vetex Connectivity Oracles

[Pettie, Yin, ICALP'21] The Structure of Minimum Vertex Cuts

[Pettie, Saranurak, Yin, STOC'22] Optimal Vertex Connectivity Oracles

Cut Query

[Rubinstein, Schramn, Weinberg, ITCS'18] Computing exact minimum cuts without knowing the graph

[Mukhopadhyay, Nanongkai, STOC'20] Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms

Reachability

Parallel

[Fineman, STOC'18] Nearly Work-Efficient Parallel Algorithm for Digraph Reachability

[Jambulapati, Liu, Sidford, STOC'19] Parallel Reachability in Almost Linear Work and Square Root Depth

[Cao, Fineman, Russell, SPAA'20] Brief Announcement: Improved Work Span Tradeoff for Single Source Reachability and Approximate Shortest Paths

CONGEST

[Nanongkai, STOC'14] Distributed Approximation Algorithms for Weighted Shortest Paths, $\tilde{O}(D+\sqrt{n}D^{1/2})$ rounds.

[Ghaffari, Udwani, PODC'15] Brief Announcement: Distributed Single-Source Reachability, $\tilde{O}(D+\sqrt{n}D^{1/4})$ rounds.

[Jambulapati, Liu, Sidford, STOC'19] Parallel Reachability in Almost Linear Work and Square Root Depth , $\tilde{O}(\sqrt{n}+n^{1/3+o(1)}D^{2/3})$ rounds.

[Parter, DISC'20] Distributed Planar Reachability in Nearly Optimal Time, planer graph in $\tilde{O}(D)$ rounds.

Diameter-Reducing Shortcuts

[Kogan, Parter, SODA'22] New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the O(√n) Barrier

[Huang, Pettie, 18] Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing Shortcuts

[Hesse, SODA'03] Directed graphs requiring large numbers of shortcuts.

Max-Flow

CONGEST

[Ghaffari, Karrenbauer, Kuhn, Lenzen, Patt-Shamir, PODC'15]. Near-Optimal Distributed Maximum Flow randomized, undirected, weighted, $(1+\epsilon)$ approximate in $O(D+\sqrt{n})\cdot n^{o(1)}\cdot \epsilon^{-3}$ rounds.

[Forster, Goranci, Liu, Peng, Sun, Ye, FOCS'21], Minor Sparsifiers and the Distributed Laplacian Paradigm.

[Anagnostides, Lenzen, Haeupler, Zuzic, Gouleakis], Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts.

Sequential

[Cohen, Madry, Sankowski, Vladu, SODA'17] Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in $\tilde{O}(m^{10/7}\log W)$ time.

[vdBLNPSSSW, FOCS'20] Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.

[vdBLLSSSW, SOTC'20] Minimum Cost Flows, MDPs, and $\ell_1$-Regression in Nearly Linear Time for Dense Instances.

[Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva, FOCS'22] Maximum Flow and Minimum-Cost Flow in Almost-Linear Time.