Zobrazeno 1 - 10
of 28
pro vyhledávání: '"Yannic Maus"'
Autor:
Yannic Maus, Tigran Tonoyan
Publikováno v:
Distributed Computing. 35:533-546
Linial’s famous color reduction algorithm reduces a given m-coloring of a graph with maximum degree $$\varDelta $$ Δ to an $$O(\varDelta ^2\log m)$$ O ( Δ 2 log m ) -coloring, in a single round in the LOCAL model. We give a similar result when no
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_________::284939aeb8aabcd5a992c86a385b3824
https://doi.org/10.1137/1.9781611977554.ch98
https://doi.org/10.1137/1.9781611977554.ch98
We study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the size of the input graph the problem can be solved in $O(\log^* n)$ roun
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6e2cfcc54a1b2462b48306d22647cd89
Autor:
Chetan Gupta, Rustam Latypov, Yannic Maus, Shreyas Pai, Simo Särkkä, Jan Studený, Jukka Suomela, Jara Uitto, Hossein Vahidi
We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in $O(\log D)$ rounds in the massively parallel computation model (MPC), with $O(n^\delta)$ words of local memory per machine, for any given consta
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::edfef69a6946ffb00c7eaa96b87e9231
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_________::15da3f7ad4664bd9d3be82c0114aa9a9
https://doi.org/10.1137/1.9781611977554.ch99
https://doi.org/10.1137/1.9781611977554.ch99
Publikováno v:
Theoretical Computer Science. 810:43-57
In the classic gossip-based model of communication for disseminating information in a network, in each time unit, every node $u$ is allowed to contact a single random neighbor $v$. If $u$ knows the data (rumor) to be disseminated, it disperses it to
Autor:
Yannic Maus
Publikováno v:
it - Information Technology. 62:271-278
Many modern systems are built on top of large-scale networks like the Internet. This article provides an overview of a dissertation [29] that addresses the complexity of classic graph problems like the vertex coloring problem in such networks. It has
Autor:
Yannic Maus
Publikováno v:
SPAA
In this paper we present a deterministic CONGEST algorithm to compute an $O(k\Delta)$-vertex coloring in $O(\Delta/k)+\log^* n$ rounds, where $\Delta$ is the maximum degree of the network graph and $1\leq k\leq O(\Delta)$ can be freely chosen. The al
Publikováno v:
Leibniz International Proceedings in Informatics (LIPIcs), 91
31st International Symposium on Distributed Computing (DISC 2017)
31st International Symposium on Distributed Computing (DISC 2017)
The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discrepancy. The directed variant of the problem requires orienting the edge
Publikováno v:
Structural Information and Communication Complexity ISBN: 9783030795269
SIROCCO
SIROCCO
This paper provides three nearly-optimal algorithms for scheduling t jobs in the \(\mathsf {CLIQUE}\) model. First, we present a deterministic scheduling algorithm that runs in \(O(\mathsf {Global}\mathsf {Congestion} + \mathsf {dilation})\) rounds f
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0d8b36ae34735805ff57e6c0cb03ca88
https://doi.org/10.1007/978-3-030-79527-6_4
https://doi.org/10.1007/978-3-030-79527-6_4