NEW HEURISTICS FOR THE PROBLEM OF CLIQUE PARTITIONING OF GRAPHS / NOVAS HEURÍSTICAS PARA O PROBLEMA DE PARTICIONAMENTO DE GRAFOS EM CLIQUES

AUTOR(ES)

SAUL GUALBERTO DE AMORIM JUNIOR

DATA DE PUBLICAÇÃO

1989

RESUMO

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.

ASSUNTO(S)

particionamento de grafos em cliques particionamento grafos partitioning clique partitioning of graphs graphs

Documentos Relacionados

• New heuristics to crew scheduling problem
• Novas heurísticas para o problema de escalonamento de atripulações
• Novas heurísticas para o problema de geração de escalas de jogos para torneios esportivos
• Novas heurísticas para o problema de geração de escalas de jogos para torneios esportivos
• Novas heurísticas para o problema de geração de escalas de jogos para torneios esportivos