10 citations · 54 across the 49 of their papers we have counts for
9 papers · 1 filter
Dynamic -Approximation Algorithms for Minimum Set Cover and Dominating Set
Shay Solomon, Amitai Uzrad
The minimum set cover (MSC) problem admits two classic algorithms: a greedy -approximation and a primal-dual -approximation, where is the universe size and is the…
Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time
Sayan Bhattacharya, Martín Costa, Nadav Panski +1
We consider the problem of maintaining a -edge coloring in a dynamic graph with nodes and maximum degree at most . The state-of-the-art update time is $O_ε(\text…
Arboricity-Dependent Algorithms for Edge Coloring
Sayan Bhattacharya, Martín Costa, Nadav Panski +1
The problem of edge coloring has been extensively studied over the years. Recently, this problem has received significant attention in the dynamic setting, where we are given a dyn…
Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in- Time Barrier
Anton Bukov, Shay Solomon, Tianyi Zhang
The dynamic set cover problem has been subject to extensive research since the pioneering works of [Bhattacharya et al, 2015] and [Gupta et al, 2017]. The input is a set system $(U…
Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenković, Solomon, and Than [CCLMST23], is a new type of graph partition into low-diameter clusters. R…
Density-Sensitive Algorithms for -Edge Coloring
Sayan Bhattacharya, Martín Costa, Nadav Panski +1
Vizing's theorem asserts the existence of a -edge coloring for any graph , where denotes the maximum degree of . Several polynomial time -edge colorin…