???item.export.label??? ???item.export.type.endnote??? ???item.export.type.bibtex???

Please use this identifier to cite or link to this item: https://tede.ufam.edu.br/handle/tede/5650
Full metadata record
DC FieldValueLanguage
dc.creatorGama, Simone Ingrid Monteiro-
dc.creator.Latteshttp://lattes.cnpq.br/1415954961112300por
dc.contributor.advisor1Rodrigues, Rosiane de Freitas-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/8358219976594707por
dc.contributor.referee1Santos , Eulanda Miranda dos-
dc.contributor.referee2Bonorno , Flávia-
dc.contributor.referee3Pio , Jose Luiz de Souza-
dc.contributor.referee4Salvatierra Junior, Mário-
dc.date.issued2016-04-19-
dc.identifier.citationGAMA, Simone Ingrid Monteiro. Sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos. 2016. 95 f. Dissertação (Mestrado em Informática) - Universidade Federal do Amazonas, Manaus, 2016.por
dc.identifier.urihttp://tede.ufam.edu.br/handle/tede/5650-
dc.description.resumoNesta dissertação, o problema da lista coloração e a propriedade da selecionabilidade em grafos são abordados. Lista coloração é uma generalização do problema da coloração de vértices em grafos, e tal como este problema clássico, consiste em colorir um grafo simples de modo que vértices adjacentes possuam cores distintas, mas, respeitando- se a restrição adicional de que cada vértice possui uma lista restrita de possíveis cores a serem usadas. Tal problema possui algumas variações, como a (g;μ)-coloração, que envolve listas sequenciais com limite inferior e superior conhecidos. A k-selecionabilidade consiste em determinar o menor tamanho de lista k para o qual sempre há uma lista coloração, seja qual for a distribuição de lista no grafo. Nesta dissertação, se investigou a correlação entre a propriedade da k-selecionabilidade e a (g;μ)-coloração, sendo definida a propriedade de k-(g;μ)-selecionabilidade. Com isto, foram também estudadas algumas técnicas de prova em selecionabilidade, aplicadas para se determinar a k-(g;μ)-selecionabilidade para classes específicas de grafos, como a técnica de degeneração em grafos, usada para provar que grafos periplanares são 3-(g;μ)-selecionáveis e a técnica de Marshal Hall, usada para provar que grafos bipartidos completos são 2-(g;μ)-selecionáveis. O resultado mais geral, obtido através de uma prova formal, consistiu em determinar que se um grafo é k-colorível, então tal grafo também é k-(g;μ)-selecionável, deixando de ser Pp 2-completo para ser NP-completo. Adicionalmente, foram estudados e implementados alguns algoritmos para determinar a lista coloração e k-selecionabilidade em grafos simples geraispor
dc.description.abstractIn this work, the list coloring problem and choosability property in graphs are investigated. List coloring is a generalization of the vertex coloring problem in graph, and as this classic problem is to color a simple graph so that adjacent vertices have different colors, but respecting the additional constraint thaht each vertex has a list of porrible colors to be used. This problem has some variations as the (g;μ)-coloring, which involves sequential lists with lower and upper bounds known. The k-choosability is to determine the smallest size list k for which there is always a valid list coloring, whatever the distribution of the list in the graph. Thus, we investigated the correlation between k-choosability and (g;μ)-coloring, porposing the k-(g;μ)-choosability property. With this, we also analysed some proof tecnhiques in choosability, applied to determine k-(g;μ)-choosability for specific graphs are 3-(g;μ)-choosable and the technique of Marshal Hall, applied to prove that complete bipartite graphs are 2-(g;μ)-choosable. The most general result, obtaines throught a relatively simple formal proof, consisted to determine if a graph is k-colorable, then this graph is algo k-(g;μ)-choosable, leaving to be Pp 2-complete for NP-complete. Additionally, it was studied and implemented some algorithms to determine the list coloration and k-choosability for simple general graphs.eng
dc.description.sponsorshipCAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superiorpor
dc.formatapplication/pdf*
dc.thumbnail.urlhttp://tede.ufam.edu.br//retrieve/16281/Disserta%c3%a7%c3%a3o%20-%20Simone%20I.%20M.%20Gama.pdf.jpg*
dc.languageporpor
dc.publisherUniversidade Federal do Amazonaspor
dc.publisher.departmentInstituto de Computaçãopor
dc.publisher.countryBrasilpor
dc.publisher.initialsUFAMpor
dc.publisher.programPrograma de Pós-graduação em Informáticapor
dc.rightsAcesso Abertopor
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/-
dc.subjectColoração em grafospor
dc.subjectComplexidade computationalpor
dc.subjectSelecionabilidade em grafospor
dc.subjectTeoria dos grafospor
dc.subject.cnpqCIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃOpor
dc.titleSobre problemas de lista coloração e a propriedade de selecionabilidade em grafospor
dc.typeDissertaçãopor
Appears in Collections:Mestrado em Informática

Files in This Item:
File Description SizeFormat 
Dissertação - Simone I. M. Gama.pdf6.03 MBAdobe PDFThumbnail

Download/Open Preview


This item is licensed under a Creative Commons License Creative Commons