10 citations · 12 across the 7 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2024
The graph alignment problem: fundamental limits and efficient algorithms
Luca Ganassali
This thesis studies the graph alignment problem, the noisy version of the graph isomorphism problem, which aims to find a matching between the nodes of two graphs which preserves m…
cs.DS2021
Correlation detection in trees for planted graph alignment
Luca Ganassali, Laurent Massoulié, Marc Lelarge
Motivated by alignment of correlated sparse random graphs, we introduce a hypothesis testing problem of deciding whether or not two random trees are correlated. We obtain sufficien…
cs.DS2020
From tree matching to sparse graph alignment
Luca Ganassali, Laurent Massoulié
In this paper we consider alignment of sparse graphs, for which we introduce the Neighborhood Tree Matching Algorithm (NTMA). For correlated Erdős-Rényi random graphs, we prove tha…