Borel oracles. An analytical approach to constant-time algorithms
Borel oracles. An analytical approach to constant-time algorithms
复制标题
Borel 神谕。
DOI：
10.1090/s0002-9939-10-10291-3
复制
发表时间：
2009
影响因子：
1.8
通讯作者：
Gábor Lippner
中科院分区：
文献类型：
--
作者：
G. Elek;Gábor Lippner
2008年，Nguyen和Onak构造了第一个常数时间算法，用于近似有界度图中的最大匹配的大小。Borel预言机是一种工具，可以用来将Borel图论中的一些语句转换为常数时间算法领域中的定理。在本文中，我们说明了这个工具的力量，以证明上述常数时间近似算法的存在性。
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.