Pantheon Repositorio Institucional
Recopila, preserva y difundi la producción académica digital en todas las áreas del conocimiento.
Comprende los activos del repositorio, además de tesis y disertaciones en la UFRJ, artículos científicos, libros electrónicos, capítulos de libros y trabajos presentados en eventos para los profesores, investigadores, personal administrativo y estudiantes de maestría y doctorado.
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/11422/1497| Especie: | Relatório |
| Título : | Clique graphs of chordal and path graphs |
| Autor(es)/Inventor(es): | Szwarcfiter, Jayme Luiz Bornstein, Claudson Ferreira |
| Resumen: | 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. |
| Resumen: | 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. |
| Materia: | Grafos cordal Algoritmos |
| Materia CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Unidade de producción: | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |
| Es parte de: | Relatório Técnico NCE |
| Número: | 2391 |
| Fecha de publicación: | 31-dic-1991 |
| País de edición : | Brasil |
| Idioma de publicación: | eng |
| Tipo de acceso : | Acesso Aberto |
| Citación : | SZWARCFITER, J. L. Clique graphs of chordal and path graphs. Rio de Janeiro: NCE, UFRJ, 1991. 11 p. (Relatório Técnico, 23/91) |
| Aparece en las colecciones: | Relatórios |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 23-91.pdf | 908.8 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.