Joakim Blikstad

activity

20192026

most citedNearly Optimal Communication and Query Complexity of Bipartite Matching

2 citations · 4 across the 16 of their papers we have counts for

collaborators

Showing 2024Show all

4 papers · 1 filter

cs.DS2024

Efficient Matroid Intersection via a Batch-Update Auction Algorithm

Joakim Blikstad, Ta-Wei Tu

Given two matroids $M_{1}$ and $M_{2}$ over the same $n$ -element ground set, the matroid intersection problem is to find a largest common independent set, whose siz…

cs.DS2024

Deterministic Online Bipartite Edge Coloring

Joakim Blikstad, Ola Svensson, Radu Vintan +1

We study online bipartite edge coloring, with nodes on one side of the graph revealed sequentially. The trivial greedy algorithm is $(2 - o (1))$ -competitive, which is optimal for gra…

cs.DS2024

Maximum Flow by Augmenting Paths in $n^{2 + o (1)}$ Time

Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak +1

We present a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from ${1, \dots, U}$ in $n^{2 + o (1)} lo g U$ time, whi…

cs.DS2024★ 1 cited

Online Edge Coloring is (Nearly) as Easy as Offline

Joakim Blikstad, Ola Svensson, Radu Vintan +1

The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree $Δ$ can be edge colored (offline) using no more than $Δ + 1$ colors (with $Δ$ being a tri…

Efficient Matroid Intersection via a Batch-Update Auction Algorithm

Deterministic Online Bipartite Edge Coloring

Maximum Flow by Augmenting Paths in n2+o(1) Time

Online Edge Coloring is (Nearly) as Easy as Offline

Maximum Flow by Augmenting Paths in $n^{2 + o (1)}$ Time