Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/43286
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorSoares, Ronan Pardo-
dc.contributor.authorPessoa, Victor Lage-
dc.date.accessioned2019-07-02T12:50:46Z-
dc.date.available2019-07-02T12:50:46Z-
dc.date.issued2019-
dc.identifier.citationPESSOA, Victor Lage. Estudo de complexidade de jogos de coloração. 2019, 66 f. Dissertação (Mestrado em Modelagem e Métodos Quantitativos) - Centro de Ciências, Universidade Federal do Ceará, 2019.pt_BR
dc.identifier.urihttp://www.repositorio.ufc.br/handle/riufc/43286-
dc.description.abstractWe answer in this dissertation a question that remained unanswered for the last 28 years: the complexity of Bodlaender’s graph coloring game. The coloring game in a simple graph G is played by two players: Alice and Bob, each has the same set of colors C having k distinct colors. In alternating turns, each chooses a single not yet colored vertex from G and a color from C used to color such vertex in a way that adjacent vertices have distinct colors. Alice wins the game when all vertices from G are properly colored and Bob wins if at any moment there is a vertex which cannot be colored by any of the k colors from C . We also studied the complexity of a variant of the game called the greed coloring game and obtained the game Grundy number for graphs of the P4 -sparse class in such game.pt_BR
dc.language.isopt_BRpt_BR
dc.subjectColoração de Grafospt_BR
dc.subjectNúmero Cromático Lúdicopt_BR
dc.subjectNúmero de Grundy Lúdicopt_BR
dc.titleEstudo de complexidade de jogos de coloraçãopt_BR
dc.typeDissertaçãopt_BR
dc.contributor.co-advisorSampaio, Rudini Menezes-
dc.description.abstract-ptbrRespondemos nesta dissertação uma questão que permaneceu em aberto nos últimos 28 anos: a complexidade do jogo de coloração em grafos de Bodlaender. O jogo de coloração em um grafo G simples é jogado por duas pessoas: Alice e Bob, cada um dispõe do mesmo conjunto de cores C com k cores distintas. Em turnos alternados, cada um escolhe apenas um vértice ainda não colorido de G e uma cor de C usada para colorir tal vértice de forma que vértices vizinhos possuam cores distintas. Alice ganha o jogo quando todos so vértices de G são propriamente coloridos e Bob ganha se em algum momento existir um vértice que não possa ser colorido com nenhuma das k cores de C . Estudamos também a complexidade de uma variante do jogo chamada de jogo de coloração gulosa e obtemos o número de Grundy lúdico para grafos da classe P4 -esparso em tal jogo.pt_BR
Aparece nas coleções:DEMA - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2019_dis_vlpessoa.pdf.pdf521,58 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.