O problema da inundação em grafos função-circular

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorAlves, Gleifer Vaz-
Autor(es): dc.contributorSouza, Uéverton dos Santos-
Autor(es): dc.creatorOmai, Mayara Midori-
Data de aceite: dc.date.accessioned2022-02-21T21:25:05Z-
Data de disponibilização: dc.date.available2022-02-21T21:25:05Z-
Data de envio: dc.date.issued2020-11-18-
Data de envio: dc.date.issued2020-11-18-
Data de envio: dc.date.issued2016-06-01-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/15939-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/652190-
Descrição: dc.descriptionThe Flood it Problem aims to determine the smallest number of movements required to convert a colored surface into a monochromatic one. Such surface can be modeled as a graph, where each vertex is a continous monochromatic region. If two regions are neighbors, then there is an edge connecting the vertices representing these regions. In a graph modeled from a colored surface, a connected subgraph composed by vertices of the same color is called monochromatic component. A movement is the assignment of a color to the vertices of a monochromatic component. There are two variations of the Flood it Problem, one is called Fixed Flood it and the other one Free Flood it. In the former, all the color assignments are made in the same monochromatic component. In the latter, it’s possible to choose a distinct monochromatic component for each movement. This paper presents a polynomial time solution for the Fixed Flood it Problem in circular-function graphs. The circular-function graphs are a new graph class defined for the first time in this work. Circular-function graphs are graphs which are intersection graphs of curves between two concentric circles, where each vertex is represented by a curve, and two vertex are neighbors if and only if their corresponding curves intersect each other. This graph class is a superclass of the co-comparability graphs, and the solution proposed in this paper is based on the solution of the Fixed Flood it Problem for co-comparability graphs, given by Fleischer and Woeginger in 2012. The solution of the Fixed Flood it Problem in circular-function graphs implies the solution to the same problem in circular trapezoid graphs, circular-arc graphs, circle graphs, circular permutation graphs, concave-round graphs, cycles, among others.-
Descrição: dc.descriptionO Problema da Inundação consiste em determinar o menor número de movimentos que tornam uma superfície, previamente colorida, monocromática. Tal superfície pode ser modelada como um grafo, onde cada vértice corresponde a uma região monocromática contínua e se duas regiões são vizinhas, então existe uma aresta entre os vértices que as representam. Considere um grafo construído a partir de uma superfície colorida. Um subgrafo conexo composto por vértices coloridos com a mesma cor é denominado componente monocromática. Um movimento se caracteriza pela atribuição de uma cor aos vértices de uma componente monocromática. Existem duas variações do Problema da Inundação, o Problema da Inundação com pivô fixo e o Problema da Inundação com pivô livre. No Problema da Inundação com pivô fixo a atribuição de cor é feita sempre na mesma componente monocromática. Já no Problema da Inundação com pivô livre pode-se escolher uma componente monocromática diferente para a atribuição de cores a cada movimento. Este trabalho apresenta uma solução em tempo polinomial para o Problema da Inundação com pivô fixo em uma classe de grafos que está sendo definida pela primeira vez neste trabalho, a classe dos grafos função-circular. Os grafos função-circular são aqueles que possuem uma representação por interseção de curvas de função entre dois círculos concêntricos, onde cada vértice é representado por uma curva e dois vértices são vizinhos se, e somente se, as curvas correspondentes se intersectam na representação. Os grafos função-circular são uma superclasse dos grafos de co-comparabilidade e a solução apresentada neste trabalho foi baseada na solução do Problema da Inundação com pivô fixo para grafos de co-comparabilidade dada por Fleischer e Woeginger em 2012. A solução do Problema da Inundação com pivô fixo em grafos função-circular implica na solução do Problema da Inundação com pivô fixo para os grafos trapézio circular, arco-circular, círculo, permutação circular, concave-round, potência de ciclo, entre outras.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherPonta Grossa-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherDepartamento Acadêmico de Informática-
Publicador: dc.publisherCiência da Computação-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Palavras-chave: dc.subjectAlgorítmos-
Palavras-chave: dc.subjectGrafos de ligação-
Palavras-chave: dc.subjectCores-
Palavras-chave: dc.subjectAlgorithms-
Palavras-chave: dc.subjectBond graphs-
Palavras-chave: dc.subjectColors-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Título: dc.titleO problema da inundação em grafos função-circular-
Título: dc.titleThe flood problem in circular-function graphs-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.