Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10332152 | Information Processing Letters | 2005 | 4 Pages |
Abstract
In this work we consider the problem of determining whether a hypergraph has the p-Helly property, when the considered subfamilies are limited by a size k. That is, whether every partial hypergraph with at most k edges is p-Helly. Further, we study the related problem applied to the cliques of a graph. In all cases, depending on the values of p and k, either we show that the problem can be solved in polynomial time, or we describe a NP-hardness proof.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mitre C. Dourado, Fábio Protti, Jayme L. Szwarcfiter,