Um Framework para Análise Seqüencial e em Paralelo de Sólidos Elásticos pelo Método dos Elementos Finitos - Dantas, Bianca de Almeida (2006)
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.