Construcao de algoritmos eficientes para problemas np-dificeis em grafos (1994)
- Authors:
- Autor USP: CARVALHEIRO, FABIO HENRIQUE - IME
- Unidade: IME
- Sigla do Departamento: MAP
- Subjects: ALGORITMOS E ESTRUTURAS DE DADOS; TEORIA DOS GRAFOS
- Language: Português
- Abstract: Arnborg (1985) e robertson/seymour (1986) introduziram, de modo independente, um conceito que se mostra uma boa medida da complexidade de um grafo g: dimensao de g (arnborg) ou tree-width de g (robertson, seymour). O primeiro autor apresenta um paradigma para desenvolver algoritmos polinomias, quando restritos a grafos com dimensao limitada para diversos problemas np-dificeis. Os outros utilizam o conceito de tree-width para resolver a conjectura well-quasi-ordering de k. Wagner e apresentar um algoritmo polinomial para o problema dos k caminhos disjuntos. O conceito de tree-width foi aproveitado por bodlander para paralelizar o paradigma de arnborg e mostrar que varios problemas np-dificeis, quando restritos a grafos com tree-width limitada, estao na classe nc. Neste trabalho apresentamos o paradigma de arnborg, generalizado e melhor formalizado, juntamente com sua aplicacao a quatro problemas np-completos, rigorosamente analisados: conjunto estavel maximo, clique maximo, coloracao minima e circuito hamiltoniano. Em seguida fazemos uma demonstracao construtiva (original) da equivalencia entre dimensao e tree-width de um grafo. Por ultimo, estudamos o problema de se determinar a dimensao (tree-width) de um dado grafo e apresentamos algumas classes de grafos com dimensao (tree-width) limitada
- Imprenta:
- Data da defesa: 01.06.1994
-
ABNT
CARVALHEIRO, Fabio Henrique. Construcao de algoritmos eficientes para problemas np-dificeis em grafos. 1994. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1994. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20220712-114614/. Acesso em: 19 abr. 2024. -
APA
Carvalheiro, F. H. (1994). Construcao de algoritmos eficientes para problemas np-dificeis em grafos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20220712-114614/ -
NLM
Carvalheiro FH. Construcao de algoritmos eficientes para problemas np-dificeis em grafos [Internet]. 1994 ;[citado 2024 abr. 19 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20220712-114614/ -
Vancouver
Carvalheiro FH. Construcao de algoritmos eficientes para problemas np-dificeis em grafos [Internet]. 1994 ;[citado 2024 abr. 19 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20220712-114614/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
