Zobrazeno 1 - 10
of 11
pro vyhledávání: '"Václav Rozhoň"'
Autor:
Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, Zoltán Vidnyánszky
Publikováno v:
Forum of Mathematics, Pi, Vol 12 (2024)
We introduce new types of examples of bounded degree acyclic Borel graphs and study their combinatorial properties in the context of descriptive combinatorics, using a generalization of the determinacy method of Marks [Mar16]. The motivation for the
Externí odkaz:
https://doaj.org/article/ef92be246f4949d4aa6213fa7423c0e2
Publikováno v:
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1e8564730049aafae0e094e6b6ad2e15
https://doi.org/10.1137/1.9781611977554.ch39
https://doi.org/10.1137/1.9781611977554.ch39
Publikováno v:
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::86de8bd77848e1c13993b025d5eed293
https://doi.org/10.1137/1.9781611977554.ch168
https://doi.org/10.1137/1.9781611977554.ch168
Publikováno v:
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
We introduce stronger notions for approximate single-source shortest-path distances, show how to efficiently compute them from weaker standard notions, and demonstrate the algorithmic power of these new notions and transformations. One application is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9e0e0d3a7963f6f231f576dc452e664e
Autor:
Mohsen Ghaffari, Václav Rozhoň
Publikováno v:
STOC
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated $2^{O(\sqrt{\log n})}$-time algorithm of Panconesi and Srinivasan [STOC'92] and settles a central and long-standing
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9a5cbd3febd44f913123cd3d4b605e6b
https://doi.org/10.1145/3357713.3384298
https://doi.org/10.1145/3357713.3384298
Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Publikováno v:
Proceedings of the 39th Symposium on Principles of Distributed Computing
PODC
PODC
Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted setting, the dependency of the complexity of the distributed Lov\'asz Local Lemma (LLL) on the chosen LLL criterion exhibits a sharp threshold phenomenon: They proved that, under
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6813f0e7b6f459be60d396d74126a50c
Publikováno v:
Electronic Notes in Discrete Mathematics. 61:743-749
Loebl, Komlos, and Sos conjectured that any graph such that at least half of its vertices have degree at least k contains every tree of order at most k + 1. We propose a skew version of this conjecture. We consider the class of trees of order at most
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::62d6b64bb129d356864445b0b4b67f2c
https://doi.org/10.1016/j.endm.2017.07.031
https://doi.org/10.1016/j.endm.2017.07.031
Publikováno v:
European Journal of Combinatorics. 88:103106
Loebl, Komlos, and Sos conjectured that any graph with at least half of its vertices of degree at least k contains every tree with at most k edges. We propose a version of this conjecture for skew trees, i.e., we consider the class of trees with at m
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::42e4ff38be3fa1dd64dd875755a9e74b
https://doi.org/10.1016/j.ejc.2020.103106
https://doi.org/10.1016/j.ejc.2020.103106
The theory of graphons comes with the so-called cut norm and the derived cut distance. The cut norm is finer than the weak* topology (when considering the predual of $L^{1}$-functions). Dole\v{z}al and Hladk\'y [J. Combin. Theory Ser. B 137 (2019), 2
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::abf93be35012469d631e769f2123d2dd
http://arxiv.org/abs/1809.03797
http://arxiv.org/abs/1809.03797
The theory of graphons is ultimately connected with the so-called cut norm. In this paper, we approach the cut norm topology via the weak* topology (when considering a predual of $L^{1}$-functions). We prove that a sequence $W_1,W_2,W_3,\ldots$ of gr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e5069fcdec0be35f566653de54aa026d
http://arxiv.org/abs/1806.07368
http://arxiv.org/abs/1806.07368