18 citations · 27 across the 26 of their papers we have counts for
4 papers · 1 filter
On the Node-Averaged Complexity of Locally Checkable Problems on Trees
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +2
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, culminati…
A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs
Alkida Balliu, Filippo Brunelli, Pierluigi Crescenzi +2
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 i…
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
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 …
Locally Checkable Labelings with Small Messages
Alkida Balliu, Keren Censor-Hillel, Yannic Maus +2
A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we s…