5 citations · 23 across the 20 of their papers we have counts for
9 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…
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…
A cubic vertex-kernel for Trivially Perfect Editing
Maël Dumas, Anthony Perez, Ioan Todinca
We consider the Trivially Perfect Editing problem, where one is given an undirected graph and a parameter and seeks to edit (add or delete) at most $…
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…
On Distance- Independent Set and other problems in graphs with few minimal separators
Pedro Montealegre, Ioan Todinca
Fomin and Villanger (STACS 2010) proved that Maximum Independent Set, Feedback Vertex Set, and more generally the problem of finding a maximum induced subgraph of treewith at most…