An algorithmic version of the blow-up lemma
An algorithmic version of the blow-up lemma
复制标题
爆炸引理的算法版本
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
E. Szemerédi
中科院分区：
文献类型：
--
作者：
J. Komlos;G. N. Sárközy;E. Szemerédi
最近我们发展了一种新的方法在图论的基础上的正则性引理。该方法被应用于稠密图中某些生成子图的寻找。除了正则性引理之外，该方法的另一个主要通用工具是所谓的爆破引理（Komlos，Sarkozy和Szemeredi [Combinatorica，17，109-123（1997）]。这个引理有助于在e-正则图中寻找有界度生成子图。我们对引理的原始证明不是算法的，它应用了概率方法。在本文中，我们提供了一个算法版本的爆破引理。对于一个n-顶点图，所需的子图可以在时间O（nM（n））内找到，其中M（n）=O（n2.376）是将两个n × n矩阵乘以整数为0，1所需的时间。我们表明，该算法可以并行化，并在NC 5中实现。© 1998 John Wiley & Sons，Inc.随机结构算法，12，297-312，1998
Recently we developed a new method in graph theory based on the regularity lemma. The method is applied to find certain spanning subgraphs in dense graphs. The other main general tool of the method, besides the regularity lemma, is the so-called blow-up lemma (Komlos, Sarkozy, and Szemeredi [Combinatorica,17, 109–123 (1997)]. This lemma helps to find bounded degree spanning subgraphs in e-regular graphs. Our original proof of the lemma is not algorithmic, it applies probabilistic methods. In this paper we provide an algorithmic version of the blow-up lemma. The desired subgraph, for an n-vertex graph, can be found in time O(nM(n)), where M(n)=O(n2.376) is the time needed to multiply two n by n matrices with 0, 1 entires over the integers. We show that the algorithm can be parallelized and implemented in NC5. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 297–312, 1998