On the kernel size of clique cover reductions for random intersection graphs
On the kernel size of clique cover reductions for random intersection graphs
复制标题
关于随机交集图的团覆盖缩减的内核大小
DOI：
10.1016/j.jda.2015.05.014
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
C. Hercher
中科院分区：
文献类型：
--
作者：
T. Friedrich;C. Hercher
用最少的团覆盖图的所有边是一个众所周知的NP-Hard问题。对于参数k是要使用的最大团数，问题变得固定参数容易处理。然而，假设指数时间假设，在最坏的情况下，不存在次指数大小的核。我们研究了具有n个顶点、边概率p和团覆盖大小为k的随机交图的平均核大小。我们考虑了Gramm，Guo，Hüffner和Niedermeier(2009)[17]的一组著名的约简规则，并证明了如果p从1有界，并且对于某个常数c>；0，k<；c对n有界，则它们大概率地完全约化了图。这表明，对于像随机交集图这样的大型概率图类，期望的核大小可以大大小于已知的指数最坏情况下界。
Covering all edges of a graph by a minimum number of cliques is a well known NP-hard problem. For the parameter k being the maximal number of cliques to be used, the problem becomes fixed parameter tractable. However, assuming the Exponential Time Hypothesis, there is no kernel of subexponential size in the worst-case. We study the average kernel size for random intersection graphs with n vertices, edge probability p, and clique covers of size k. We consider the well-known set of reduction rules of Gramm, Guo, Hüffner, and Niedermeier (2009)[17] and show that with high probability they reduce the graph completely if p is bounded away from 1 and k< c log n for some constant c> 0. This shows that for large probabilistic graph classes like random intersection graphs the expected kernel size can be substantially smaller than the known exponential worst-case bounds.
登录
查看更多内容
随机交叉图及其在安全、无线通信和社交网络中的应用
DOI：
--
发表时间：
2015
期刊：
arXiv.org
影响因子：
--
作者：
Jun Zhao;Osman Yağan;V. Gligor
通讯作者：
V. Gligor
使用人工资源约束在传统 VLIW 调度程序中处理不规则 ILP
DOI：
--
发表时间：
2000
期刊：
International Conference on Compilers, Architecture, and Synthesis for Embedded Systems
影响因子：
--
作者：
Subramanian Rajagopalan;Manish Vachharajani;S. Malik
通讯作者：
S. Malik
无标度网络上的参数化团
DOI：
--
发表时间：
2012
期刊：
International Symposium on Algorithms and Computation
影响因子：
--
作者：
T. Friedrich;Anton Krohmer
通讯作者：
Anton Krohmer
DOI：
--
发表时间：
1993
期刊：
Comb.
影响因子：
--
作者：
B. Bollobás;P. Erdös;J. Spencer;D. West
通讯作者：
D. West
DOI：
--
发表时间：
2001
期刊：
International Workshop on Graph-Theoretic Concepts in Computer Science
影响因子：
--
作者：
Maw;H. Müller
通讯作者：
H. Müller