Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1985
Type: Relatório
Title: A generalization of the helly property applied to the cliques of a graph
Author(s)/Inventor(s): Dourado, Mitre Costa
Protti, Fábio
Szwarcfiter, Jayme Luiz
Abstract: Let p ≥ 1 and q ≥ 0 be integers. A family S of sets is (p,q)-intersecting when every subfamily S' ⊆ S formed by p or less members has total intersection of cardinality at least q. A family F of sets is (p,q)-Helly when every (p,q)-intersecting subfamily F' ⊆ F has total intersection of cardinality at least q. A graph G is a (p, q)- clique-Helly graph when its family of cliques (maximal complete sets) is (P, q)-Helly. According to this terminology, the usual Helly property and the clique-Helly graphs correspond to the case p = 2, q = 1. In this work we present characterizations for (p,q)-Helly families of sets and (p,q)-clique-Helly graphs. For fixed p,q those characterizations lead to polynomial-time recognition algorithms. When p or q is not fixed, it is shown that the recognition of (p,q)-clique-Helly graphs is NP-hard. We also extend further the notions presented, by defining the (p,q, r)-Helly property (which holds when every (p, q)-intersecting subfamily F' ⊆ F has total intersection of cardinality at least r) and giving a way of recognizing (p, q, r)-Helly families in terms of the (p, q)-Helly property.
Keywords: Grafo clique
Teoria dos grafos
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Department : Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Issue: 0102
Issue Date: 31-Dec-2002
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Citation: DOURADO, M. C. ; PROTTI, F. ; SZWARCFITER, J. L.A generalization of the helly property applied to the cliques of a graph. Rio de Janeiro: NCE, UFRJ, 2002. 25 p. (Relatório Técnico, 01/02)
URI: http://hdl.handle.net/11422/1985
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
01_02_000613309.pdf1,2 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.