Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/2657
Tipo: Relatório
Título: A representation for the modules of a graph and applications
Autor(es)/Inventor(es): Klein, Sulamita
Szwarcfiter, Jayme Luiz
Resumo : 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.
Palavras-chave: Grafos
Algoritmos
Algorithms
Graphs
Assunto CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO
Departamento: Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Número: 2099
Data de publicação: 31-Dez-1999
País de publicação: Brasil
Idioma da publicação: eng
Tipo de acesso: Acesso Aberto
Citação: 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
Aparece nas coleções:Relatórios Técnicos e de Pesquisa

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
20_99_000611310.pdf829,1 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.