Algoritmos Paralelos para Extensão Linear em Digrafos Planares

Abstract

O objetivo principal deste trabalho consistiu em estudar e detalhar o algoritmo paralelo PRAM para computar a extensão linear de um digrafo acíclico planar, devido a Kao e Klein [KAO93]. Para digrafos acíclicos gerais, a obtenção de uma extensão linear não é simples. Kao e Klein mostraram que no modelo PRAM ela só pode ser obtida por meio da computação do fecho transitivo do digrafo. Para a classe dos digrafos acíclicos planares, Kao e Klein apresentam um algoritmo paralelo PRAM para computar a extensão linear sem a necessidade de computar o fecho transitivo do digrafo. Esse algoritmo, entretanto, utiliza uma série de estruturas e definições próprias de teoria dos grafos, além de outros algoritmos para resolver problemas chaves em digrafos. Dentre estes, o principal algoritmo estudado foi o algoritmo paralelo PRAM para obtenção de árvores geradoras em digrafos fortemente conexos, denominado algoritmo do CD-PAR, devido a Kao e Shannon [KAO89]. Kao e Klein mostraram que, partindo do resultado do algoritmo do CD-PAR, pode-se obter uma decomposição em orelhas de digrafos acíclicos planares e, a partir desta, alcançar a extensão linear. Essa relação entre árvores geradoras e decomposição em orelhas é a base para o entendimento do algoritmo de extensão linear proposto por Kao e Klein e amplamente discutida neste trabalho.

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.