Zobrazeno 1 - 10
of 43
pro vyhledávání: '"Shay Solomon"'
Autor:
Shay Solomon
Publikováno v:
Journal of Computational Geometry, Vol 6, Iss 2 (2015)
$\newcommand{\eps}{\epsilon}$A spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree is called a shallow-light tree (shortly, SLT). More specifically, an $(\alpha,\beta)$-SLT of a weighted undirected graph $G
Externí odkaz:
https://doaj.org/article/c5ba5ef39c814bfa94109d4c150ec1c4
Autor:
Shay Solomon, Amitai Uzrad
Publikováno v:
Proceedings of the 55th Annual ACM Symposium on Theory of Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b985244b45430b39162fac6a22ddfa28
https://doi.org/10.1145/3564246.3585211
https://doi.org/10.1145/3564246.3585211
Autor:
Haim Kaplan, Shay Solomon
Publikováno v:
SPAA
In 1999, Brodal and Fagerberg (BF) gave an algorithm for maintaining a low outdegree orientation of a dynamic uniformly sparse graph. Specifically, for a dynamic graph on n -vertices, with arboricity bounded by ɑ at all times, the BF algorithm suppo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b791979e9d1038a7d7790f47dd0d9da0
https://doi.org/10.1145/3434395
https://doi.org/10.1145/3434395
Autor:
Shay Solomon, Nicole Wein
Publikováno v:
ACM Transactions on Algorithms. 16:1-24
This paper studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within $n^{1-\epsilon}$ for any $\epsilon > 0$, is NP-hard in static graphs, there i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5f247cbfe893177f62c572013a28de04
https://doi.org/10.1145/3392724
https://doi.org/10.1145/3392724
Autor:
Hung Le, Shay Solomon
Seminal works on light spanners over the years have provided spanners with optimal lightness in various graph classes, such as general graphs, Euclidean spanners, and minor-free graphs. Three shortcomings of previous works on light spanners are: (i)
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::176e0e9417fa02eaa46e0b0833c3e071
http://arxiv.org/abs/2008.10582
http://arxiv.org/abs/2008.10582
Autor:
Lazar Milenkovic, Shay Solomon
Publikováno v:
SPAA
The neighborhood independence number of a graph G, denoted by β = β(G), is the size of the largest independent set in the neighborhood of any vertex. Graphs with bounded neighborhood independence, already for constant β, constitute a wide family o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::47bbb33e53b4baaed5b80c784027af40
https://doi.org/10.1145/3350755.3400248
https://doi.org/10.1145/3350755.3400248
We study the matching problem in the incremental setting, where we are given a sequence of edge insertions and aim at maintaining a near-maximum cardinality matching of the graph with small update time. We present a deterministic algorithm that, for
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::847adf09434e30bc71474be851a7c662
Autor:
Hung Le, Shay Solomon
Publikováno v:
FOCS
Euclidean spanners are important geometric structures, having found numerous applications over the years. Cornerstone results in this area from the late 80s and early 90s state that for any $d$-dimensional $n$-point Euclidean space, there exists a $(
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::05b1974b406396d46c2867b780fc7b30
https://doi.org/10.1109/focs.2019.00069
https://doi.org/10.1109/focs.2019.00069