Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/2657
Type: Relatório
Title: A representation for the modules of a graph and applications
Author(s)/Inventor(s): Klein, Sulamita
Szwarcfiter, Jayme Luiz
Abstract: We describe a simple representation for the modules of a graph C. We show that the modules of C are in one-to-one correspondence with the ideaIs of certain posets. These posets are characterizaded and shown to be layered posets, that is, transitive closures of bipartite tournaments. Additionaly, we describe applications of the representation. Employing the above correspondence, we present methods for solving the following problems: (i) generate alI modules of C, (ii) count the number of modules of C, (iii) find a maximal module satisfying some hereditary property of C and (iv) find a connected non-trivial module of C.
Keywords: Teoria dos grafos
Algoritmos
Algorithms
Graphs
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO
Department : Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Issue: 2099
Issue Date: 31-Dec-1999
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Citation: KLEIN, S.; SZWARCFITER, J. L. A representation for the modules of a graph and applications. Rio de Janeiro: NCE, UFRJ, 1999. 17 p. (Relatório Técnico, 20/99)
URI: http://hdl.handle.net/11422/2657
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
20_99_000611310.pdf829,1 kBAdobe PDFView/Open


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