file.pdf (357.49 kB)
Download file

Looking for vertex number one

Download (357.49 kB)
journal contribution
posted on 15.05.2015, 00:00 by Alan FriezeAlan Frieze, Wesley Pegden

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(log4 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(log4 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.




Usage metrics