Enumerating the maximal cliques of a circle graph
| dc.citation.issue | 1488 | pt_BR |
| dc.creator | Szwarcfiter, Jayme Luiz | |
| dc.creator | Barroso, Magali M. Araujo | |
| dc.date.accessioned | 2017-03-17T12:22:30Z | |
| dc.date.available | 2026-05-16T03:03:32Z | |
| dc.date.issued | 1988-12-31 | |
| dc.description.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. | en |
| dc.description.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). | pt_BR |
| dc.embargo.terms | aberto | pt_BR |
| dc.identifier.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) | pt_BR |
| dc.identifier.uri | http://hdl.handle.net/11422/1592 | |
| dc.language | por | pt_BR |
| dc.publisher.country | Brasil | pt_BR |
| dc.publisher.department | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais | pt_BR |
| dc.relation.ispartof | Relatório Técnico NCE | pt_BR |
| dc.rights | Acesso Aberto | pt_BR |
| dc.subject | Teoria dos grafos | pt_BR |
| dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | pt_BR |
| dc.title | Enumerating the maximal cliques of a circle graph | pt_BR |
| dc.type | Relatório | pt_BR |