[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. / [en] The clique partitioning problem arise very often in many
fields as Social Science, Economics, Biology, Cluster
analysis and in all other fields that need a
classification of elements. The main exact algorithms and
heuristics that appear in the literature are studied. A
especial class of instances of the clique partitioning
problem for which the most comonly used heuristics perform
arbitrarily bad is exhibited. Four new heuristics are
presented and two of them are based on the known simulated
anneling and tabu search methods. They are analised by
their application to test-problems, real-life-problems and
to the special class of instances mentioned above
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:9882 |
| Date | 10 May 2007 |
| Creators | SAUL GUALBERTO DE AMORIM JUNIOR |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0079 seconds