2 citations · 4 across the 16 of their papers we have counts for
4 papers · 1 filter
Greedy Algorithms for Shortcut Sets and Hopsets
Ben Bals, Joakim Blikstad, Greg Bodwin +3
For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentiall…
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Aaron Bernstein, Joakim Blikstad, Jason Li +2
We give a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time,…
Online Edge Coloring: Sharp Thresholds
Joakim Blikstad, Ola Svensson, Radu Vintan +1
Vizing's theorem guarantees that every graph with maximum degree admits an edge coloring using colors. In online settings - where edges arrive one at a time and must be…
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay +1
A recent breakthrough by [LNPSY STOC'21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequ…