Pantheon Institutional repository
Collect, preserve and disseminate digital academic production in all areas of knowledge.
Comprise the assets of the repository, in addition to theses and dissertations at UFRJ, scientific articles, electronic books, book chapters and papers presented at events for teachers, researchers, administrative staff and students of master's and doctoral degrees.
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11422/1592| Type: | Relatório |
| Title: | Enumerating the maximal cliques of a circle graph |
| Author(s)/Inventor(s): | Szwarcfiter, Jayme Luiz Barroso, Magali M. Araujo |
| Abstract: | 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). |
| Abstract: | 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. |
| Keywords: | Teoria dos grafos |
| Subject CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Production unit: | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |
| In: | Relatório Técnico NCE |
| Issue: | 1488 |
| Issue Date: | 31-Dec-1988 |
| Publisher country: | Brasil |
| Language: | por |
| Right access: | Acesso Aberto |
| Citation: | 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) |
| Appears in Collections: | Relatórios |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 14_88_000040359.pdf | 973.83 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.