ࡱ> ,.+bjbjUU >??  0 ' 3Z;;;;;;;;;;;;×3;;w0;;;;<;;;;;;;;;;;;;;;;;;;;;;;;; :Resumo Dado um grafo G=(V,E) e um limitante ( ( (0,1], uma (-clique qualquer subconjunto C de V tal que a densidade do grafo induzido em G por C maior ou igual a (. O problema da (-clique de cardinalidade mxima consiste em determinar um subconjunto de cardinalidade mxima C* dos ns de V tal que a densidade do grafo induzido em G por C* seja maior ou igual ao limitante (. Na primeira parte dessa dissertao, prope-se um algoritmo exato para o problema da quase-clique mxima, baseado em uma propriedade quase-hereditria. Experimentos computacionais mostram que o novo algoritmo competitivo com as melhores formulaes exatas da literatura resolvidas pelo CPLEX. O algoritmo tambm fornece uma nova cota superior que consistentemente mais justa do que as cotas j conhecidas. Na segunda parte da dissertao, prope-se a hibridizao de um algoritmo gentico com chaves aleatrias tendenciosas com o algoritmo exato desenvolvido na primeira parte da dissertao. Resultados computacionais mostram que o enfoque hbrido tem melhor desempenho do que o algoritmo gentico original. Palavras-chave: Problema da quase-clique de cardinalidade mxima; problema da quase-clique mxima; problema da clique mxima; grafos; algoritmos genticos baseados em chaves aleatrias; metaheursticas; densidade do grafo. Abstract Given a graph G=(V,E) and a threshold ( ( (0,1], a (-clique is any subset C of V such that the density of the graph induced in G by C is greater than or equal to (. The maximum cardinality (-clique problem amounts to finding a maximum cardinality subset C* of the vertices in V such that the density of the graph induced in G by C* is greater than or equal to the threshold (. In the first part of this dissertation, we propose an exact algorithm for solving the maximum quasi-clique problem, based on a quasi-hereditary property. Computational experiments show that the new algorithm is competitive with the best formulations in the literature solved by CPLEX. The algorithm also provides a new upper bound that is consistently tighter than previously existing bounds. In the second part of this dissertation, we propose a hybridization of a biased random-key genetic algorithm with the exact algorithm developed in the first part of the dissertation. Computational results show that the hybrid approach outperforms the original genetic algorithm. Keywords: Maximum cardinality quasi-clique problem; maximum quasi-clique problem; maximum clique problem; graphs; biased random-key genetic algorithms; metaheuristics; graph density.   "#,-./08;<=z { | }        t 7 8 T z E F U a b g h hOha&mHsHh Lha&mHsH jha& jgha&he\ha&mHsHha&mHsH"hmha&5CJ \aJ mHsHHF G & ' ( 1 2 KLgdg0gde\$a$gdm$a$gdm & ( 1 2 X Y Z [ e f 12W{JKLɻд´ддд´ддд he\ha& jha& jgha& hOha&ha&hmha&5CJ \aJ hmha&mHsHhe\ha&mHsHha&mHsH/<P1h:pG/ =!"#$% Dpj  666666666666666666666666666666666666666666 6666666666 666666666666 6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~ OJPJQJ_HmHnHsHtHN`N GNormal dCJ^J_HaJmH sH tH DA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List PK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK]      _GoBack( ( g0Ge\uSma&O L  @ @@UnknownG*Ax Times New Roman5Symbol3" Arial7.@CalibriACambria Math"ZYZYs!0$P e\!xxResumo Celso RibeiroHelioOh+'0  < H T`hpxResumoCelso RibeiroNormal_WordconvHelio2Microsoft Office Outlook@G@\y3@\y3s՜.+,0 hp|   Resumo Title  !"$%&'()*-Root Entry F0̗3/1TableWordDocument>SummaryInformation(DocumentSummaryInformation8#CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q