10.1184/R1/6478232.v1 Alan Frieze Alan Frieze Wesley Pegden Wesley Pegden Looking for vertex number one Carnegie Mellon University 2015 Mathematical Sciences 2015-05-15 00:00:00 Journal contribution https://kilthub.cmu.edu/articles/journal_contribution/Looking_for_vertex_number_one/6478232 <p>Given an instance of the preferential attachment graph Gn = ([n], En), we would like to find vertex 1, using only ‘local’ information about the graph; that is, by exploring the neighborhoods of small sets of vertices. Borgs et. al gave a O(log<sup>4</sup> n) algorithm, which is local in the sense that at each step, it needs only search the neighborhood of a set of vertices of size O(log<sup>4</sup> n). We give a faster algorithm to find vertex 1, which is local in the strongest sense of operating only on neighborhoods of sets of size 1.</p>