10 citations · 23 across the 21 of their papers we have counts for
Showing 2023 · cs.DSShow all
3 papers · 2 filters
cs.DS2023
Simple and Asymptotically Optimal Online Bipartite Edge Coloring
Joakim Blikstad, Ola Svensson, Radu Vintan +1
We provide a simple online -edge-coloring algorithm for bipartite graphs of maximum degree under adversarial vertex arrivals on one side of the graph. Our…
cs.DS2023
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
Sayan Bhattacharya, Peter Kiss, Aaron Sidford +1
We study dynamic -approximate rounding of fractional matchings -- a key ingredient in numerous breakthroughs in the dynamic graph algorithms literature. Our first contributi…
cs.DS2023★ 1 cited
Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
Joseph, Naor, Aravind Srinivasan +1
We introduce the abstract problem of rounding an unknown fractional bipartite -matching revealed online (e.g., output by an online fractional algorithm), exposed node-b…