Zobrazeno 1 - 10
of 85
pro vyhledávání: '"Balliu, Alkida"'
Autor:
Balliu, Alkida, Ghaffari, Mohsen, Kuhn, Fabian, Modanese, Augusto, Olivetti, Dennis, Rabie, Mikaël, Suomela, Jukka, Uitto, Jara
By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is locally checkable labeling problems (LCLs), introduced by Naor and Stockme
Externí odkaz:
http://arxiv.org/abs/2407.05445
Autor:
Balliu, Alkida, Brandt, Sebastian, Kuhn, Fabian, Nowicki, Krzysztof, Olivetti, Dennis, Rotenberg, Eva, Suomela, Jukka
Algorithms with advice have received ample attention in the distributed and online settings, and they have recently proven useful also in dynamic settings. In this work we study local computation with advice: the goal is to solve a graph problem $\Pi
Externí odkaz:
http://arxiv.org/abs/2405.04519
The node-averaged complexity of a problem captures the number of rounds nodes of a graph have to spend on average to solve the problem in the LOCAL model. A challenging line of research with regards to this new complexity measure is to understand the
Externí odkaz:
http://arxiv.org/abs/2405.01366
We study the complexity of fundamental distributed graph problems in the recently popular setting where information about the input graph is available to the nodes before the start of the computation. We focus on the most common such setting, known a
Externí odkaz:
http://arxiv.org/abs/2405.00825
Over the past decade, a long line of research has investigated the distributed complexity landscape of locally checkable labeling (LCL) problems on bounded-degree graphs, culminating in an almost-complete classification on general graphs and a comple
Externí odkaz:
http://arxiv.org/abs/2308.04251
A temporal graph is a graph in which edges are assigned a time label. Two nodes u and v of a temporal graph are connected one to the other if there exists a path from u to v with increasing edge time labels. We consider the problem of assigning time
Externí odkaz:
http://arxiv.org/abs/2304.00817
We show fast deterministic algorithms for fundamental problems on forests in the challenging low-space regime of the well-known Massive Parallel Computation (MPC) model. A recent breakthrough result by Coy and Czumaj [STOC'22] shows that, in this set
Externí odkaz:
http://arxiv.org/abs/2211.03530
We investigate the distributed complexity of maximal matching and maximal independent set (MIS) in hypergraphs in the LOCAL model. A maximal matching of a hypergraph $H=(V_H,E_H)$ is a maximal disjoint set $M\subseteq E_H$ of hyperedges and an MIS $S
Externí odkaz:
http://arxiv.org/abs/2211.01945
Autor:
Balliu, Alkida, Brandt, Sebastian, Fischer, Manuela, Latypov, Rustam, Maus, Yannic, Olivetti, Dennis, Uitto, Jara
Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent se
Externí odkaz:
http://arxiv.org/abs/2208.09453
The node-averaged complexity of a distributed algorithm running on a graph $G=(V,E)$ is the average over the times at which the nodes $V$ of $G$ finish their computation and commit to their outputs. We study the node-averaged complexity for some dist
Externí odkaz:
http://arxiv.org/abs/2208.08213