Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/1497
Tipo: Relatório
Título: Clique graphs of chordal and path graphs
Autor(es)/Inventor(es): Szwarcfiter, Jayme Luiz
Bornstein, Claudson Ferreira
Resumo: Nós caracterizamos os grafos clique de grafos cordiais e de caminhos. É apresentada ainda uma classe de grafos chamada árvores expandidas. Elas formam uma sub-classe dos grafos disk-Helly. Mostra-se que o grafo clique de todo grafo cordal (portanto dos de caminho) é uma árvore expandida. Mais ainda, que toda árvore expandida é o grafo clique de algum grafo de caminho (portanto cordal). Diferentes caracterizações de árvores expandidas são descritas, conduzindo a um algoritmo de tempo polinomial para o reconhecimento de grafos nesta classe.
Resumo : We characterize clique graphs of chordal and path graphs. A special class of graphs called expanded trees is introduced. They form a subclass of disk-Helly graphs. It is shown that the clique graph of every chordal (hence path) graph is an expanded tree. In addition, every expanded tree is the clique graph of some path (hence chordal) graph. Different characterizations of expanded trees are described, leading to a polynomial time algorithm for recognizing clique graphs of chordal and path graphs.
Palavras-chave: Grafos cordal
Algoritmos
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: 2391
Data de publicação: 31-Dez-1991
País de publicação: Brasil
Idioma da publicação: eng
Tipo de acesso: Acesso Aberto
Citação: SZWARCFITER, J. L. Clique graphs of chordal and path graphs. Rio de Janeiro: NCE, UFRJ, 1991. 11 p. (Relatório Técnico, 23/91)
URI: http://hdl.handle.net/11422/1497
Aparece nas coleções:Relatórios Técnicos e de Pesquisa

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
23-91.pdf908,8 kBAdobe PDFVisualizar/Abrir


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