On the Independence Number of Random Interval Graphs
On the Independence Number of Random Interval Graphs
复制标题
关于随机区间图的独立数
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
E. Z. De La V E
中科院分区：
文献类型：
--
作者：
S. B. O U C H E R O N;W. F E R N;A. Nd;E. Z. De La V E
一个随机区间图的顺序n是通过挑选2n个数字X1：X2 n独立于均匀分布0; 1]，并考虑收集n个区间的端点X2 i？1和X 2 i，对于i 2 f1;：：：ng。图的顶点对应于区间。如果相应的区间相交，则两个顶点相连。本文刻画了随机区间图的独立数的涨落。这个特征是通过对贪婪算法的分析得到的。我们实际上证明了极限定理（中心极限定理和大偏差原理）的阶段数的贪婪算法。证明依赖于通过随机水平的第一通过时间的分析。
A random interval graph of order n is generated by picking 2n numbers X 1 : : : X 2n independently from the uniform distribution on 0; 1] and considering the collection of n intervals with extremities X 2i?1 and X 2i for i 2 f1;:::ng. The graph vertices correspond to intervals. Two vertices are connected if the corresponding intervals intersect. This paper characterizes the uctuations of the independence number in random interval graphs. This characterization is obtained through the analysis of the greedy algorithm. We actually prove limit theorems (central limit theorem and large deviation principle) on the number of phases of this greedy algorithm. The proof relies on the analysis of rst-passage-times through a random level.