[en] NEW HEURISTICS FOR THE PROBLEM OF CLIQUE PARTITIONING OF GRAPHS

• Ano de defesa: 2007
• Autor(a) principal: SAUL GUALBERTO DE AMORIM JUNIOR
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] GRAFO; [pt] PARTICIONAMENTO; [pt] PARTICIONAMENTO DE GRAFOS EM CLIQUES; [en] GRAPH; [en] PARTITIONING; [en] CLIQUE PARTITIONING OF GRAPHS
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=9882&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=9882&idi=2; http://doi.org/10.17771/PUCRio.acad.9882

[pt] O problema de particionamento de grafos em cliques ocorre freqüentemente em diversas áreas tais como Ciências sociais, Ciências Econômicas, Biologia, Análise de Agrupamentos e em todas as áreas onde é necessário a classificação de elementos. Estuda-se aqui os principais algoritmos exatos e as principais heurísticas que constam na literatura. É feita uma análise do desempenho das heurísticas no pior caso e apresenta-se uma classe especial de problemas para os quais o seu desempenho é arbitrariamente ruim. Apresentam-se quatro novas heurísticas para o problema, duas delas baseadas nos métodos conhecidos por simulated anneling e por tabu search. Elas são comparadas entre si através da análise dos resultados de suas aplicações a problemas-teste, a problemas que ocorre na realidade e a classe de problemas especiais mencionada acima.