аЯрЁБс>ўџ 13ўџџџ0џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅСq`№П"bjbjqPqP4::"џџџџџџЄьььььььDDDD P Ю .hhhhhCCCM O O O O O O $ќ hd @s ьCCCCCs ььhhлˆ йййCьhьhM йCM ййььйh\ p?$šЖеDIjйA ž 0Ю йЄ ГЄ ййЄ ьэTCCйCCCCCs s Я CCCЮ CCCCDDDььььььџџџџ Resumo: Em 1972, Richard Karp apresentou ao mundo a prova de NP-completude de 21 problemas fundamentais para a Ciъncia da Computaчуo. Feedback Vertex Set e Conjunto Independente sуo dois destes problemas clсssicos. Feedback Vertex Set consiste em encontrar um conjunto mэnimo de nѓs que se removidos elimina todos os ciclos presentes no grafo de entrada. Conjunto Independente, por sua vez, consiste em determinar um conjunto mсximo de vщrtices dois a dois nуo adjacentes. Nesta dissertaчуo, estudamos o problema de determinar se um dado grafo de entrada G possui um conjunto feedback-independente, i.e., um conjunto que щ mutualmente feedback vertex set e independente. Grafos que admitem conjunto feedback-independente sуo conhecidos na literatura como grafos quase-bipartidos e o reconhecimento de tal classe щ NP-completo para grafos em geral. Nesta dissertaчуo, focamos em instтncias pertencentes р classe dos grafos distтncia-hereditсrios (DHG). Esta classe de grafos apresentada por Howorka em 1977 tem como caracterэstica principal preservar a distтncia dos vщrtices em qualquer subgrafo induzido e conexo. Grafos distтncia-hereditсrios sуo uma superclasse dos cografos. A escolha desta classe foi motivada pela existъncia de estudos anteriores sobre cografos que admitem conjuntos feedback-independentes. Utilizando uma estrutura de decomposiчуo dos grafos distтncia-hereditсrios, semelhante р cotree dos cografos, construэmos um algoritmo de programaчуo dinтmica capaz de determinar em tempo polinomial se um dado grafo distтncia-hereditсrio possui um conjunto feedback-independente. Tal algoritmo utiliza as caracterэsticas de cada tipo de elemento da decomposiчуo para elaboraчуo de relaчѕes de recorrъncia da programaчуo dinтmica. Palavras-chave: Conjunto Feedback-Independente, DHG, Programaчуo Dinтmica, Decomposiчуo de grafos. Abstract: In 1972, Richard Karp introduced to the world the NP-completeness proof of 21 fundamental problems for Computer Science. Feedback Vertex Set and Independent Set are two of these classical problems. Feedback Vertex Set consists in finding minimal vertex set that, if it is removed, eliminates all entry graph cycles. Independent Set, on the other hand, consists on determining a maximum set of two-by-two nonadjacent vertices. In this dissertation, we study the problem of determining if a given input graph G has an Independent Feedback Vertex Set (IFVS), in other words, a set that is mutually feedback vertex set and independent. Graphs that support independent feedback vertex set are known in the literature as near-bipartite graphs, and the recognition of such a class is NP-complete for graphs in general. In this dissertation, we focus on instances belonging to the class of distance-hereditary graphs (DHG). This class of graphs presented by Howorka in 1977 has as its main characteristic to preserve the distance of vertices in any induced and connected subgraph. Distance-hereditary graphs are a superclass of the cographs. The choice of this class was motivated by the existence of previous studies on cographs which allow independent feedback vertex sets. Using a decomposition tree of distance-hereditary graphs, similar to the cotree of cographs, we built a dynamic programming algorithm capable of determining in polynomial time whether a given distance-hereditary graph has an independent feedback vertex set. Such algorithm uses the characteristics of each decomposition tree element type to the elaboration of dynamic programming recurrence relations. Keywords: Independent Feedback Vertex Set, DHG, Dynamic Programming, graph-decomposition.  б67AЦЧвјџ  !"ѕцлѕЫИлЉИ”И”ИЉ…hYFЪhŠOJQJmH sH (hYFЪh|>*B*OJQJmH phsH hYFЪh|OJQJmH sH %hYFЪh|B*OJQJmH phsH hYFЪB*OJQJmH phsH hYFЪh|OJQJhYFЪh|B*OJQJphhYFЪhYFЪOJQJ вг67AЧШ"юююююцццюю$a$gdYFЪ$d№Є7$8$H$a$gdYFЪ "§21h:pиQзА‚. АЦA!АЅ"АЅ#‰$‰%ААФАФ Ф†œ˜žžžžžžžž666666666vvvvvvvvv666666>666666666666666666666666666Ј6666666666И666666666666hH66666666666666666666666666666666666666666666666666666666666666666А6J@ёџJ иQзNormal dЄШCJ_HaJmHsHtH >AђџЁ> Fonte parсg. padrуoTiѓџГT 0 Tabela normalі4ж l4жaі ,kєџС, 0 Sem lista žeђž Š0Prщ-formataчуo HTMLA Ц2”(М Pфx  4 Ш#\'№*„.2Ќ5@9d№ЄCJOJPJQJ^JaJtHHўЂH Š0 Char CharCJOJPJQJ^JaJtHRўOёџR gSem EspaчamentoCJ_HaJmHsHtH "џџџџ вг67AЧ Ш $˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€" " "№8№@ёџџџ€€€ї№’№№0№( № №№B №S №ПЫџ ?№>K–счp{…‹/:›Бпцcy !Wm}ƒќї ў h p “  Ѕ ­ ў  ~ „ ˆ  $‡ирAIМФz} npьє$7A$$ыKuхТ" fзW+й@Vх:hе+y|Š3!Žg lВž)ЖYFЪиQзa<ы$џ@€ЂЂ˜Z=ъъЂЂ"@@џџUnknownџџџџџџџџџџџџGџ:рAxР џTimes New Roman5€Symbol3& џ:рCxР џArial7&џрџЌ@ŸCalibri?5 џ:рCxР џCourier New"qˆ№ФЉНy'м›|‡=5э 5э !№Ѕ‰ДД242ƒ№ќ§HP-№џ$PфџџџџџџџџџџџџџџџџџџџџџŠ2џџvictorHelioўџр…ŸђљOhЋ‘+'Гй0TˆœЈИФд ф№   (4<DLфvictorNormalHelio2Microsoft Office Word@Ў‡…@Fz­frе@8б šЖе5э ўџеЭеœ.“—+,љЎ0ш hp|„Œ” œЄЌД М Щфц  Tэtulo ўџџџўџџџўџџџ!"#$%&'ўџџџ)*+,-./ўџџџ§џџџ2ўџџџўџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџRoot Entryџџџџџџџџ РFp„A$šЖе4€Data џџџџџџџџџџџџ1TableџџџџWordDocumentџџџџ4SummaryInformation(џџџџџџџџџџџџ DocumentSummaryInformation8џџџџџџџџ(CompObjџџџџџџџџџџџџuџџџџџџџџџџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџўџ џџџџ РF#Documento do Microsoft Office Word MSWordDocWord.Document.8є9Вq