Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/1755
Tipo: Artigo de Periódico
Título: Finding All Maximal Contiguous Subsequences of a Sequence of Numbers in O(1) Communication Rounds
Autor(es): Alves, Carlos Eduardo Rodrigues
Cáceres, Edson Norberto
Song, Siang Wun
Abstract: Given a sequence A of real numbers, we wish to find a list of all nonoverlapping contiguous subsequences of A that are maximal. A maximal subsequence M of A has the property that no proper subsequence of M has a greater sum of values. Furthermore, M may not be contained properly within any subsequence of A with this property. This problem has several applications in Computational Biology and can be solved sequentially in linear time. We present a BSP/CGM algorithm that solves this problem using p processors in O(|A|=p) time and O(|A|=p) space per processor. The algorithm uses a constant number of communication rounds of size at most O(|A|=p). Thus, the algorithm achieves linear speedup and is highly scalable. To our knowledge, there are no previous known parallel BSP/CGM algorithms to solve this problem.
Palavras-chave: Otimização Combinatória
Combinatorial Optimization
Arquiteturas e Programação Paralelas
Parallel Architecture and Programming
Algoritmos e Estruturas de Dados
Algorithms and Data Structures
Teoria da Computação
Theory of Computation
Editor: IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Citação: ALVES, Carlos Eduardo Rodrigues; CÁCERES, Edson Norberto; SONG, Siang Wun. Finding All Maximal Contiguous Subsequences of a Sequence of Numbers in O(1) Communication Rounds. Ieee Transactions On Parallel And Distributed Systems, v. 4, n. 24, p.724-733, abr. 2013. Disponível em: <http://doi.ieeecomputersociety.org/10.1109/TPDS.2012.149>. Acesso em: 06 ago. 2013.
Tipo de acesso: Acesso Aberto
Identificador DOI: http://dx.doi.org/10.1109/TPDS.2012.149
URI: https://repositorio.ufms.br/handle/123456789/1755
Data do documento: Abr-2013
Aparece nas coleções:FACOM - Artigos publicados em periódicos

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Resumo.pdf77,9 kBAdobe PDFThumbnail
Visualizar/Abrir


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