作者： Fabio Protti , Jayme Luiz Szwarcfiter , Mitre Costa Dourado
DOI:
关键词: Recognition algorithm 、 Mathematics 、 Discrete mathematics 、 Family of sets 、 Graph 、 Combinatorics 、 Subfamily
摘要: Let p > 1 and q 0 be integers. A family of sets F is (p, q)-intersecting when every subfamily F' ⊆ formed by or less members has total intersection cardinality at least q. ' (p,q)-Helly (p,q)-intersecting graph G a (p,q)-clique-Helly its (maximal) cliques q)-Helly. According to this terminology, the usual Helly property clique-Helly graphs correspond case = 2, 1. In work we present characterization for q)-clique-Helly graphs. For fixed p, q, leads polynomial-time recognition algorithm. When not fixed, it shown that NP-hard.