Algoritmos Paralelos para Extensão Linear em Digrafos Planares

AUTOR(ES)

Anderson Correa de Lima

DATA DE PUBLICAÇÃO

2006

RESUMO

This work main objective was to study and to detail a PRAM parallel algorithm to compute topological ordering of a planar acyclic digraph, proposed by Kao and Klein. It is not trivial to obtain a topological ordering of general acyclic digraphs. Kao and Klein showed that this ordering can only be achieved computing the digraph transitive closure. Concerning to planar acyclic digraphs, Kao and Klein proposed a PRAM parallel algorithm for computing topological ordering without computing the digraph transitive closure. However this algorithm uses a sort of data structures and definitions from Graph Theory, beyond other algorithms for solving some graph related key problems. Among these algorithms, we focused on a PRAM parallel algorithm for obtaining spanning trees in strongly connected digraphs. This algorithm was proposed by Kao and Shannon and is named CD-PAIR algorithm. Kao and Klein showed that, based on this algorithm result, it is possible to obtain an ear decomposition of planar acyclic digraphs and, further achieve a topological ordering. This relation between spanning trees and ear decomposition is the most important concept for the total comprehension of the Kao and Klein s topological ordering algorithm widely discussed on this work.

ASSUNTO(S)

planar acyclic digraph pram parallel algorithm ciencia da computacao algoritmo paralelo pram digrafo acíclico planar

Documentos Relacionados

• Produtos de kronecker, simetrizadoras e algoritmos paralelos e sequenciais na algebra linear
• Algoritmos paralelos para o problema da mochila.
• Algoritmos paralelos realísticos para a maior subsequência comum
• Avaliação de algoritmos de ordenação em sistemas paralelos
• Algoritmos heuristicos e exatos para resolução do problema de sequenciamento em processadores paralelos