作者
Bruno Coelho Coutinho, Hai-Jun Zhou, Yang-Yu Liu
发表日期
2020/5/17
期刊
Physical Review Letters
简介
We introduce two generalizations of core percolation in graphs to hypergraphs, related to the minimum hyperedge cover problem and the minimum vertex cover problem on hypergraphs, respectively. We offer analytical solutions of these two core percolations for uncorrelated random hypergraphs whose vertex degree and hyperedge cardinality distributions are arbitrary but have nondiverging moments. We find that for several real-world hypergraphs their two cores tend to be much smaller than those of their null models, suggesting that covering problems in those real-world hypergraphs can actually be solved in polynomial time.
学术搜索中的文章
BC Coutinho, AK Wu, HJ Zhou, YY Liu - Physical Review Letters, 2020