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. / In this work we consider a problem from the Anthropology. The model of the societies and the marriages of individuals is done with mixed graphs and to find disjoint paths is a central question in the problem. The problem is NP-complete and W[1]-hard when it is considered a parameterized problem. Some subproblems that arise during the process to obtain a solution for the problem, involve disjoint paths and can be solved in polynomial time. We implemented some polynomial algorithms that are used in a tool developed to solve the problem in the Anthropology considered. Our solution worked well for the societies provided by our partners.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-13022014-083516 |
| Date | 18 December 2013 |
| Creators | Álvaro Junio Pereira Franco |
| Contributors | Carlos Eduardo Ferreira, Marcelo Henriques de Carvalho, Marcia Rosana Cerioli, Orlando Lee, Jose Coelho de Pina Junior |
| Publisher | Universidade de São Paulo, Ciência da Computação, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0028 seconds