Covering Problems and Core Percolations on Hypergraphs.
Phys Rev Lett
; 124(24): 248301, 2020 Jun 19.
Article
en En
| MEDLINE
| ID: mdl-32639824
ABSTRACT
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.
Texto completo:
1
Colección:
01-internacional
Base de datos:
MEDLINE
Idioma:
En
Revista:
Phys Rev Lett
Año:
2020
Tipo del documento:
Article
País de afiliación:
Portugal