Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/1985
Tipo: Relatório
Título: A generalization of the helly property applied to the cliques of a graph
Autor(es)/Inventor(es): Dourado, Mitre Costa
Protti, Fábio
Szwarcfiter, Jayme Luiz
Resumo : 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.
Palavras-chave: Grafo clique
Teoria dos grafos
Assunto CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Departamento: Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Número: 0102
Data de publicação: 31-Dez-2002
País de publicação: Brasil
Idioma da publicação: eng
Tipo de acesso: Acesso Aberto
Citação: 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
Aparece nas coleções:Relatórios Técnicos e de Pesquisa

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
01_02_000613309.pdf1,2 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.