6 papers
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…
Even-Cycle Detection in the Randomized and Quantum CONGEST Model
Pierre Fraigniaud, Mael Luce, Frederic Magniez +1
We show that, for every , -freeness can be decided in rounds in the \CONGEST{} model by a randomized Monte-Carlo distributed algorithm with one-side…
Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing
Arthur Braida, Simon Martiel, Ioan Todinca
Quantum annealing (QA) holds promise for optimization problems in quantum computing, especially for combinatorial optimization. This analog framework attracts attention for its pot…
Distributed Treewidth Computation and Courcelle's Theorem in the CONGEST Model
Benjamin Jauregui, Jason Li, Pedro Montealegre +1
Algorithmic meta-theorems, stating that graph properties expressible in some particular logic can be decided efficiently in graph classes having some specific structural properties…
Deterministic Even-Cycle Detection in Broadcast CONGEST
Pierre Fraigniaud, Maël Luce, Frédéric Magniez +1
We show that, for every , -freeness can be decided in rounds in the Broadcast CONGEST model, by a deterministic algorithm. This (deterministic) roun…
Polynomial kernels for edge modification problems towards block and strictly chordal graphs
Maël Dumas, Anthony Perez, Mathis Rocton +1
We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph and an integer and seeks to…