ࡱ> )+(2bjbjUU >??2  0        Y[[[[[[[     [  p      Y  Y    ؀  E0 z z z <        [[        z          :Novos algoritmos para o problema do Corte Global de Colorao Mnima Resumo O Problema do Corte Global de Colorao Mnima (PCGCM) definido conforme segue: dado um grafo conexo (no-direcionado) G com arestas coloridas, o objetivo encontrar um corte de arestas E' de G (um conjunto minimal de arestas cuja remoo transforma o grafo em desconexo) tal que o nmero de cores usadas nas arestas em E' seja mnimo. No conhecida a complexidade computacional deste problema, embora Faria et al. [10] tenham demonstrado que o PCGCM NP-completo se o grafo de entrada for um digrafo. Neste trabalho, so apresentadas duas abordagens (determinstica e probabilstica) baseadas na metaheurstica Variable Neighborhood Search para resolver este problema. Os algoritmos apresentados so capazes de achar todas as solues timas conhecidas na literatura. Palavras-chave: Problema do Corte Global de Colorao Minima, Otimizaao Combinatria, Teoria dos Grafos, Variable Neighborhood Search, Problema do Corte Rotulado. Abstract The Minimum Coloring Cut Problem (MCCP) is defined as follows: given a connected (undirected) graph G with colored edges, find an edge cut E' of G (a minimal set of edges whose removal renders the graph disconnected) such that the number of colors used by the edges in E' is minimum. The computational complexity of this problem is unknown, although Faria et al. [10] have demonstrated that the MCCP is NP-complete if the input graph is a digraph. In this work, two approaches (deterministic and probabilistic) are presented based on Variable Neighborhood Search to solve this problem. The presented algorithms are able to find all the optimum solutions described in the literature. Keywords: Minimum Coloring Cut Problem, Combinatorial Optimization, Graph Theory, Variable Neighborhood Search, Label Cut Problem. )+35FM T  12ľhh>\^JmH sH hLh>\mH sH h>\^JmH sH hh>\mH sH "hLh>\5CJ$\aJ$mH sH  h>\^J hLh>\hh>\6]h>\hLh>\5CJ$\aJ$h>\5CJ0\aJ0hLh>\5CJ0\aJ0EFMT  2gd$a$gd$a$gd <P1h:p>\. A!"#$% Dpj 666666666vvvvvvvvv666666>6666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~ OJPJQJ_HmHnHsHtHR`R Normal d CJPJ^J_HaJmHsHtH 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] 222 >\]tLXiV/g24@2@@UnknownG*Ax Times New Roman5Symbol3" Arial7.@CalibriACambria Math":X':X'!0$P2!xxDNovos algoritmos para o problema do Corte Global de Colorao MnimaAugusto Cesar Bordini BragaHelioOh+'0$0H Xd   HNovos algoritmos para o problema do Corte Global de Colorao MnimaAugusto Cesar Bordini BragaNormal_WordconvHelio3Microsoft Office Outlook@@@՜.+,04 hp   Petrobras ENovos algoritmos para o problema do Corte Global de Colorao Mnima Title !"#$%&'*Root Entry FĹ؀,1Table zWordDocument>SummaryInformation(DocumentSummaryInformation8 CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q