BOREL ORACLES. AN ANALYTICAL APPROACH TO CONSTANT-TIME ALGORITHMS

作     者：Elek, Gabor Lippner, Gabor 

作者机构：Hungarian Acad Sci Alfred Renyi Inst H-1364 Budapest Hungary Eotvos Lorand Univ Dept Comp Sci H-117 Budapest Hungary 

出 版 物：《PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY》 (美国数学会会报)

年 卷 期：2010年第138卷第8期

页      面：2939-2947页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：OTKA [67867  69062] 

主　　题：Constant time algorithms graph limits Borel graphs invariant measures maximum matching 

摘      要：In 2008 Nguyen and Onak constructed the first constant-time algorithm for the approximation of the size of the maximum matching in bounded degree graphs. The Borel oracle machinery is a tool that can be used to convert some statements in Borel graph theory to theorems in the field of constant-time algorithms. In this paper we illustrate the power of this tool to prove the existence of the above mentioned constant-time approximation algorithm.