Zobrazeno 1 - 10
of 150
pro vyhledávání: '"Solomon, Shay"'
Vizing's Theorem from 1964 states that any $n$-vertex $m$-edge graph with maximum degree $\Delta$ can be {\em edge colored} using at most $\Delta + 1$ colors. For over 40 years, the state-of-the-art running time for computing such a coloring, obtaine
Externí odkaz:
http://arxiv.org/abs/2410.12479
Autor:
Assadi, Sepehr, Behnezhad, Soheil, Bhattacharya, Sayan, Costa, Martín, Solomon, Shay, Zhang, Tianyi
Vizing's theorem states that any $n$-vertex $m$-edge graph of maximum degree $\Delta$ can be \emph{edge colored} using at most $\Delta + 1$ different colors [Vizing, 1964]. Vizing's original proof is algorithmic and shows that such an edge coloring c
Externí odkaz:
http://arxiv.org/abs/2410.05240
Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic "compactness'' measures of a Euclidean spanner $E$ are the size (number of edges) $|E|$ and the weight (sum of edge weights) $\|
Externí odkaz:
http://arxiv.org/abs/2409.08227
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 $n$ elements and a fixed collection of $m$ sets, where each element appears in a most $
Externí odkaz:
http://arxiv.org/abs/2407.06431
Vizing's theorem states that any $n$-vertex $m$-edge graph of maximum degree $\Delta$ can be {\em edge colored} using at most $\Delta + 1$ different colors [Diskret.~Analiz, '64]. Vizing's original proof is algorithmic and shows that such an edge col
Externí odkaz:
http://arxiv.org/abs/2405.15449
A $(1+\varepsilon)\textit{-stretch tree cover}$ of a metric space is a collection of trees, where every pair of points has a $(1+\varepsilon)$-stretch path in one of the trees. The celebrated $\textit{Dumbbell Theorem}$ [Arya et~al. STOC'95] states t
Externí odkaz:
http://arxiv.org/abs/2403.17754
Autor:
Solomon, Shay, Uzrad, Amitai
The minimum set cover (MSC) problem admits two classic algorithms: a greedy $\ln n$-approximation and a primal-dual $f$-approximation, where $n$ is the universe size and $f$ is the maximum frequency of an element. Both algorithms are simple and effic
Externí odkaz:
http://arxiv.org/abs/2312.17625
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 dynamic graph evolving via a sequence of edge insertions and deletions an
Externí odkaz:
http://arxiv.org/abs/2311.08367
We consider the problem of maintaining a $(1+\epsilon)\Delta$-edge coloring in a dynamic graph $G$ with $n$ nodes and maximum degree at most $\Delta$. The state-of-the-art update time is $O_\epsilon(\text{polylog}(n))$, by Duan, He and Zhang [SODA'19
Externí odkaz:
http://arxiv.org/abs/2311.03267
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, S)$ on a fixed collection $S$ of sets and a dynamic universe of elem
Externí odkaz:
http://arxiv.org/abs/2308.00793