Complexity aspects of generalized Helly hypergraphs |
| |
Authors: | Mitre C. Dourado Jayme L. Szwarcfiter |
| |
Affiliation: | a COPPE - Universidade Federal do Rio de Janeiro, Caixa Postal 2324, Rio de Janeiro, RJ, Brazil b Instituto de Matemática and NCE, Brazil c Instituto de Matemática, NCE and COPPE, Brazil |
| |
Abstract: | In [V.I. Voloshin, On the upper chromatic number of a hypergraph, Australas. J. Combin. 11 (1995) 25-45], Voloshin proposed the following generalization of the Helly property. Let p?1, q?0 and s?0. A hypergraph H is (p,q)-intersecting when every partial hypergraph H′⊆H formed by p or less hyperedges has intersection of cardinality at least q. A hypergraph H is (p,q,s)-Helly when every partial (p,q)-intersecting hypergraph H′⊆H has intersection of cardinality at least s. In this work, we study the complexity of determining whether H is (p,q,s)-Helly. |
| |
Keywords: | Helly property Helly hypergraphs Intersecting sets Computational complexity Combinatorial problems |
本文献已被 ScienceDirect 等数据库收录! |
|