Description
Abstract:
Let G be a graph and p: V(G) -> R an embedding of its vertices into the line. The unlabeled reconstruction problem is the following: given the (multi-)set of edge lengths of (G,p), determine both G and p. This problem is known to be NP-hard; however, in a recent preprint, Connelly, Gortler and Theran gave an algorithm that, for a uniform random embedding p, solves the reconstruction problem with high probability, provided that G is 3-connected. In the talk I will describe the ideas behind their algorithm.
The talk will be in English.