Use este identificador para citar ou linkar para este item: http://repositorio.bc.ufg.br/handle/ri/19276
Tipo do documento: Artigo
Título: Polynomial enumeration of chordless cycles on cyclically orientable graphs
Autor: Castonguay, Diane
Dias, Elisângela Silva
Abstract: In a nite undirected simple graph, a chordless cycle is an induced subgraph which is a cycle. A graph is called cyclically orientable if it admits an orientation in which every chordless cycle is cyclically oriented. We propose an algorithm to enumerate all chordless cycles of such a graph. Compared to other similar algorithms, the proposed algorithm has the advantage of nding each chordless cycle only once in time complexity O(n2), where n is the number of vertices.
Palavras-chave: Chordless cycles
Cyclically orientable graphs
País: Brasil
Unidade acadêmica: Instituto de Informática - INF (RG)
Citação: CASTONGUAY, Daine; DIAS, Elisângela Silva. Polynomial enumeration of chordless cycles on cyclically orientable graphs. Matematica Contemporanea, Rio de Janeiro, v. 44, p. 1-10, 2015.
Tipo de acesso: Acesso Aberto
Endereço da licença: http://creativecommons.org/licenses/by-nc-nd/4.0/
URI: http://repositorio.bc.ufg.br/handle/ri/19276
Data de publicação: 2015
Aparece nas coleções:INF - Artigos publicados em periódicos

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Artigo - Diane Castonguay - 2015.pdf252,36 kBAdobe PDFThumbnail
Baixar/Abrir


Este item está licenciada sob uma Licença Creative Commons Creative Commons