10 citations · 54 across the 49 of their papers we have counts for
6 papers · 1 filter
Even Faster -Edge Coloring via Shorter Multi-Step Vizing Chains
Sayan Bhattacharya, Martín Costa, Shay Solomon +1
Vizing's Theorem from 1964 states that any -vertex -edge graph with maximum degree can be {\em edge colored} using at most colors. For over 40 years, the state-of-…
Vizing's Theorem in Near-Linear Time
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3
Vizing's theorem states that any -vertex -edge graph of maximum degree can be edge colored using at most different colors [Vizing, 1964]. Vizing's original proof i…
Towards Instance-Optimal Euclidean Spanners
Hung Le, Shay Solomon, Cuong Than +2
Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic "compactness'' measures of a Euclidean spanner are the…
A Lossless Deamortization for Dynamic Greedy Set Cover
Shay Solomon, Amitai Uzrad, Tianyi Zhang
The dynamic set cover problem has been subject to growing research attention in recent years. In this problem, we are given as input a dynamic universe of at most elements and…
Faster -Edge Coloring: Breaking the Time Barrier
Sayan Bhattacharya, Din Carmon, Martín Costa +2
Vizing's theorem states that any -vertex -edge graph of maximum degree can be {\em edge colored} using at most different colors [Diskret.~Analiz, '64]. Vizing's or…
Optimal Euclidean Tree Covers
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
A of a metric space is a collection of trees, where every pair of points has a -stretch path in one of the trees. The…