Enumerating the maximal cliques of a circle graph

Szwarcfiter, Jayme Luiz; Barroso, Magali M. Araujo

Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1592

Full metadata record

DC Field	Value	Language
dc.contributor.author	Szwarcfiter, Jayme Luiz	-
dc.contributor.author	Barroso, Magali M. Araujo	-
dc.date.accessioned	2017-03-17T12:22:30Z	-
dc.date.available	2023-12-21T03:02:49Z	-
dc.date.issued	1988-12-31	-
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.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.language	por	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.title	Enumerating the maximal cliques of a circle graph	pt_BR
dc.type	Relatório	pt_BR
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.publisher.country	Brasil	pt_BR
dc.publisher.department	Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais	pt_BR
dc.subject.cnpq	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO	pt_BR
dc.citation.issue	1488	pt_BR
dc.embargo.terms	aberto	pt_BR
Appears in Collections:	Relatórios

Files in This Item:

File	Description	Size	Format
14_88_000040359.pdf		973.83 kB	Adobe PDF	View/Open

Show simple item record Recommend this item View Statistics

Pantheon Institutional repository