LOOKING FOR VERTEX NUMBER ONE

• 成果类型: Article
• 署名作者: Frieze, Alan; Pegden, Wesley
• 署名单位: Carnegie Mellon University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/16-AAP1212
• 发表日期: 2017
• 页码: 582-630
• 关键词: free random graph

摘要

Given an instance of the preferential attachment graph G(n) = ([n], E-n), 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 an algorithm which runs in time O(log(4) n), which is local in the sense that at each step, it needs only to search the neighborhood of a set of vertices of size O(log(4) n). We give an algorithm to find vertex 1, which w.h.p. runs in time O (omega log n) and which is local in the strongest sense of operating only on neighborhoods of single vertices. Here co = co (n) is any function that goes to infinity with n.