Algoritmos para junções em digrafos acíclicos e uma aplicação na Antropologia

• Ano de defesa: 2013
• Autor(a) principal: Franco, Álvaro Junio Pereira
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: acyclic digraph; algorithms for junctions; algoritmos para junções; antropologia estrutural; caminhos disjuntos; complexidade computacional; computational complexity; digrafos acíclicos; disjoint paths; structural anthropology
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13022014-083516/

Neste trabalho consideramos um problema da Antropologia. A modelagem de sociedades e casamentos de indivíduos é feita com grafos mistos e encontrar caminhos disjuntos é uma questão central no problema. O problema é NP-completo e, quando visto como um problema parametrizado, ele é W[1]-difícil. Alguns subproblemas que surgem durante o processo de obter uma solução para o problema, envolvem caminhos disjuntos e podem ser resolvidos em tempo polinomial. Implementamos algoritmos polinomiais que são usados em uma ferramenta desenvolvida para solucionar o problema na Antropologia considerado. Nossa solução funcionou bem para as sociedades fornecidas pelos nossos parceiros.