Pantheon Repositório Institucional da UFRJ
Coleta, preserva e divulga a produção acadêmica digital em todas as áreas do conhecimento.
São os ativos do repositório, além de teses e dissertações da UFRJ, artigos científicos, livros eletrônicos, capítulos de livros e trabalhos apresentados em eventos por professores, pesquisadores, funcionários administrativos e alunos de mestrado e doutorado.
Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/11422/1592| Tipo: | Relatório |
| Título: | Enumerating the maximal cliques of a circle graph |
| Autor(es)/Inventor(es): | Szwarcfiter, Jayme Luiz Barroso, Magali M. Araujo |
| Resumo: | Descrevemos a noção de orientação localmente transitiva de um grafo não direcionado, como uma generalização de orientação transitiva ordinária. Com aplicação obtemos um algoritmo para a geração de todas as cliques maximais de um grafo circular G, cuja complexidade é 0(n(m+α)), onde n, m e a são o número de vértices, arestas e cliques maximais de G. Em adição, mostraremos que o número exato de tais cliques pode ser computado em tempo 9(nm). |
| Resumo: | We describe the notion of locally transitive orientations of an undirected graph, as a generalization of ordinarytransitive orientations. As an application, we obtain an algorithm for generating all maximal cliquesof a circle graph G in time 0(n(m+α)), where n,m and a are the number of vertices, edges and maximal cliques of G. In addition, we show that the actual number of such cliques can be computedin 0(nm) time. |
| Palavras-chave: | Teoria dos grafos |
| Assunto CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Unidade produtora: | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |
| In: | Relatório Técnico NCE |
| Número: | 1488 |
| Data de publicação: | 31-Dez-1988 |
| País de publicação: | Brasil |
| Idioma da publicação: | por |
| Tipo de acesso: | Acesso Aberto |
| Citação: | SZWARCFITER, J. L.; BARROSO, M. M. A. Enumerating the maximal cliques of a circle graph. Rio de Janeiro: NCE, UFRJ, 1988. 8 p. (Relatório Técnico, 14/88) |
| Aparece nas coleções: | Relatórios |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 14_88_000040359.pdf | 973.83 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.