13 citations · 26 across the 10 of their papers we have counts for
8 papers · 1 filter
Deterministic Distributed DFS and Other Problems via Cycle Separators in Planar Graphs
Benjamin Jauregui, Pedro Montealegre, Ivan Rapaport
One of the most basic techniques in algorithm design consists of breaking a problem into subproblems and then proceeding recursively. In the case of graph algorithms, one way to im…
Strong and Hiding Distributed Certification of Bipartiteness
Benjamin Jauregui, Augusto Modanese, Pedro Montealegre +1
In this paper, we study the problem of certifying whether a graph is bipartite (i.e. -colorable) with a locally checkable proof (LCP) that is able to hide a -coloring from th…
Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
Pedro Montealegre, Diego Ramírez-Romero, Iván Rapaport
We present compact distributed interactive proofs for the recognition of two important graph classes, well-studied in the context of centralized algorithms, namely complement reduc…
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…
Shared vs Private Randomness in Distributed Interactive Proofs
Pedro Montealegre, Diego Ramírez-Romero, Ivan Rapaport
In distributed interactive proofs, the nodes of a graph G interact with a powerful but untrustable prover who tries to convince them, in a small number of rounds and through short…
Compact Distributed Certification of Planar Graphs
Laurent Feuilloley, Pierre Fraigniaud, Ivan Rapaport +3
Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a \emph{distributed interactive proof} for planarity (i.e., for certifying that a network is planar)…