1 citations · 1 across the 9 of their papers we have counts for
11 papers
Improved Euclidean Shallow Light Trees
Hung Le, Shay Solomon, Cuong Than +2
For parameters , a spanning tree of a weighted graph rooted at a designated vertex is called an -shallow-light tree (SLT) if (i) for every vertex ,…
Approximating Euclidean Shallow-Light Trees
Hung Le, Shay Solomon, Cuong Than +2
For a weighted graph and a designated source vertex , a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source and a minimum…
Vizing's Theorem in Deterministic Almost-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's original proof is easily transl…
Covering the Euclidean Plane by a Pair of Trees
Hung Le, Lazar Milenković, Shay Solomon +1
A {-stretch tree cover} of a metric space , for a parameter , is a collection of trees such that every pair of points has a -stretch path in one of the tr…
Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
An La, Hung Le, Shay Solomon +4
It is known that any -point set in the -dimensional Euclidean space , for , admits: 1) a -spanner with maximum degree and…
Approximate Light Spanners in Planar Graphs
Hung Le, Shay Solomon, Cuong Than +2
In their seminal paper, Althöfer et al. (DCG 1993) introduced the {\em greedy spanner} and showed that, for any weighted planar graph , the weight of the greedy -spanner…
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…