5 citations · 15 across the 23 of their papers we have counts for
4 papers · 1 filter
What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
Lélia Blin, Fedor V. Fomin, Pierre Fraigniaud +5
The question of 'what can be computed locally?' lies at the heart of distributed computing in networks. As established in Naor and Stockmeyer's seminal paper (STOC 1993), this ques…
Distributed Model Checking on Graphs of Bounded Treedepth
Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre +2
We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the CONGEST model. To our knowl…
The Minimum Clique Routing Problem on Cycles
Mariana Escalante, Martín Matamala, Iván Rapaport +2
In the Minimum Clique Routing Problem on Cycles \textsc{MCRPC} we are given a cycle together with a set of demands (weighted origin-destination pairs) and the goal is to route all…
Tiling with bars under tomographic constraints
Christoph Durr, Eric Goles, Ivan Rapaport +1
We wish to tile a rectangle or a torus with only vertical and horizontal bars of a given length, such that the number of bars in every column and row equals given numbers. We prese…