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
Department : 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)
URI: http://hdl.handle.net/11422/1592
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
14_88_000040359.pdf973,83 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.