Mostrar el registro sencillo del ítem
dc.contributor.author
Costa Dourado, Mitre
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Grippo, Luciano Norberto
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Safe, Martin Dario
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2024-01-25T15:25:27Z
dc.date.issued
2023-05
dc.identifier.citation
Costa Dourado, Mitre; Grippo, Luciano Norberto; Safe, Martin Dario; On the generalized Helly property of hypergraphs, cliques, and bicliques; Elsevier Science; Discrete Applied Mathematics; 330; 5-2023; 56-77
dc.identifier.issn
0166-218X
dc.identifier.uri
http://hdl.handle.net/11336/224886
dc.description.abstract
A family of sets is (p,q)-intersecting if every nonempty subfamily of p or fewer sets has at least q elements in its total intersection. A family of sets has the (p,q)-Helly property if every nonempty (p,q)-intersecting subfamily has total intersection of cardinality at least q. The (2,1)-Helly property is the usual Helly property. A hypergraph is (p,q)-Helly if its edge family has the (p,q)-Helly property and hereditary (p,q)-Helly if each of its subhypergraphs has the (p,q)-Helly property. A graph is (p,q)-clique-Helly if the family of its maximal cliques has the (p,q)-Helly property and hereditary (p,q)-clique-Helly if each of its induced subgraphs is (p,q)-clique-Helly. The classes of (p,q)-biclique-Helly and hereditary (p,q)-biclique-Helly graphs are defined analogously. In this work, we prove several characterizations of hereditary (p,q)-Helly hypergraphs, including one by minimal forbidden partial subhypergraphs. On the algorithmic side, we give an improved time bound for the recognition of (p,q)-Helly hypergraphs for each fixed q and show that the recognition of hereditary (p,q)-Helly hypergraphs can be solved in polynomial time if p and q are fixed and co-NP-complete if p is part of the input. In addition, we generalize the characterization of p-clique-Helly graphs in terms of expansions to (p,q)-clique-Helly graphs and give different characterizations of hereditary (p,q)-clique-Helly graphs, including one by forbidden induced subgraphs. We give an improvement on the time bound for the recognition of (p,q)-clique-Helly graphs and prove that the recognition problem of hereditary (p,q)-clique-Helly graphs is polynomial-time solvable for p and q fixed and NP-hard if p or q is part of the input. Finally, we provide different characterizations, give recognition algorithms, and prove hardness results for (p,q)-biclique-Helly graphs and hereditary (p,q)-biclique-Helly graphs which are analogous to those for (p,q)-clique-Helly and hereditary (p,q)-clique-Helly graphs.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/restrictedAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
FORBIDDEN INDUCED SUBGRAPHS
dc.subject
FORBIDDEN PARTIAL SUBHYPERGRAPHS
dc.subject
GENERALIZED HELLY PROPERTY
dc.subject
HELLY HYPERGRAPHS
dc.subject
MAXIMAL BICLIQUES
dc.subject
MAXIMAL CLIQUES
dc.subject
RECOGNITION ALGORITHMS
dc.subject.classification
Matemática Aplicada
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
On the generalized Helly property of hypergraphs, cliques, and bicliques
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2024-01-23T14:51:54Z
dc.journal.volume
330
dc.journal.pagination
56-77
dc.journal.pais
Países Bajos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Costa Dourado, Mitre. Universidade Federal do Rio de Janeiro; Brasil
dc.description.fil
Fil: Grippo, Luciano Norberto. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina
dc.description.fil
Fil: Safe, Martin Dario. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Bahía Blanca. Instituto de Matemática Bahía Blanca. Universidad Nacional del Sur. Departamento de Matemática. Instituto de Matemática Bahía Blanca; Argentina. Universidad Nacional del Sur. Departamento de Matemática; Argentina
dc.journal.title
Discrete Applied Mathematics
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X23000094
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2023.01.006
Archivos asociados