Locally Dense Independent Sets in Regular Graphs of Large Girth - An Example of a New Approach
Locally Dense Independent Sets in Regular Graphs of Large Girth - An Example of a New Approach
复制标题
大周长正则图中的局部密集独立集 - 新方法的示例
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
L. Margulis
中科院分区：
文献类型：
--
作者：
L. Margulis
我们提出了一个新的方法，似乎适用于每一个图形的理论概念定义的局部条件和定期图的大围长的例子。它结合了一个随机的外部程序处理的图形轮与一个几乎任意的算法解决每个轮内的本地实例，并结合本地解决方案的全球之一。所考虑实例的局部一致性和外部过程的随机性使得渐近分析成为可能。在这里，我们将这种方法应用于局部定义的图论概念的最简单但最基本的例子：图中的独立集。
We present an example for a new approach which seems applicable to every graph theoretical concept defined by local conditions and regular graphs of large girth. It combines a random outer procedure processing the graph in rounds with a virtually arbitrary algorithm solving local instances within each round and combines the local solutions to a global one. The local uniformity of the considered instances and the randomness of the outer procedure make the asymptotic analysis possible. Here we apply this approach to the simplest yet fundamental example of a locally defined graph theoretical concept: independent sets in graphs.