首页 | 本学科首页   官方微博 | 高级检索  
     


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 HH 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 HH 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号