13 citations · 23 across the 6 of their papers we have counts for
6 papers
Local Certification of Graphs with Bounded Genus
Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre +3
Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as i…
On the Complexity of the Stability Problem of Binary Freezing Totalistic Cellular Automata
Eric Goles, Diego Maldonado, Pedro Montealegre +1
In this paper we study the family of two-state Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square grids with von Neumann neighborhoods. We say that…
Competing Activists--Political Polarization
Lucas Böttcher, Pedro Montealegre, Eric Goles +1
Recent empirical findings suggest that societies have become more polarized in various countries. That is, the median voter of today represents a smaller fraction of society compar…
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…
PSPACE-Completeness of Majority Automata Networks
Eric Goles, Pedro Montealegre, Ville Salo +1
We study the dynamics of majority automata networks when the vertices are updated according to a block sequential updating scheme. In particular, we show that the complexity of the…
Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre +1
In this paper we give upper bounds on the number of minimal separators and potential maximal cliques of graphs w.r.t. two graph parameters, namely vertex cover (…