Coloração de arestas em grafos split-comparabilidade e split-intervalos

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-8639-3532-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9151881548763857-
Autor(es): dc.contributorSilva, Candida Nunes da-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-4649-0274-
Autor(es): dc.contributorhttp://lattes.cnpq.br/6019111128413167-
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-8639-3532-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9151881548763857-
Autor(es): dc.contributorMiranda, Alberto Alexandre Assis-
Autor(es): dc.contributorhttp://lattes.cnpq.br/7105752672122742-
Autor(es): dc.contributorSales, Claudia Linhares-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-5290-5173-
Autor(es): dc.contributorhttp://lattes.cnpq.br/6115379961132154-
Autor(es): dc.contributorZatesko, Leandro Miranda-
Autor(es): dc.contributorhttp://lattes.cnpq.br/4259616811045288-
Autor(es): dc.creatorGonzaga, Luis Gustavo da Soledade-
Data de aceite: dc.date.accessioned2022-02-21T22:15:14Z-
Data de disponibilização: dc.date.available2022-02-21T22:15:14Z-
Data de envio: dc.date.issued2021-08-20-
Data de envio: dc.date.issued2021-08-20-
Data de envio: dc.date.issued2021-04-20-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/25776-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/671072-
Descrição: dc.descriptionA proper edge coloring of a graph is an assignment of colors to its edges such that edges incident with the same vertex have distinct colors. The Edge Coloring Problem is answering, given a graph, which is the least number of colors for a proper edge coloring. That number is called the chromatic index and, for a graph 𝐺, it is denoted 𝜒′ (𝐺). By definition, the chromatic index is at least ∆(𝐺), wherein ∆(𝐺) is the largest number of edges incident with the same vertex of the graph 𝐺. In 1964, Vizing proved that 𝜒′(𝐺) ≤ ∆(𝐺) + 1 for every simple graph 𝐺. Therefore, when 𝐺 is a simple graph, ∆(𝐺) ≤ 𝜒′(𝐺) ≤ ∆(𝐺)+1. A graph is Class 1 if its chromatic index equals its maximum degree, and it is Class 2 otherwise. The Graph Classification Problem is deciding if a simple graph is Class 1. Even considering that there are only two possible values for the chromatic index, the Graph Classification Problem is still NP-complete. In 1985, in his famous column "The NP-Completeness Column: an Ongoing Guide”, David Johnson classified some problems in Graph Theory concerning their computational complexity. In some cases, that complexity was still unknown and Johnson identified graph classes for which he considered it would be easier to determine it. On the classes of split, comparability, and intervals graphs, for instance, Johnson considered that determining the computational complexity of the Classification Problem was possibly easy. However, after 35 years, only the computational complexity of the Classification Problem for comparability graphs was determined, being it an NP-complete problem. This thesis presents a polynomial-time solution for the Classification Problem for splitinterval graphs, besides identifying and correcting an issue in the previous proof that determined the chromatic index of split-comparablility graphs.-
Descrição: dc.descriptionCoordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)-
Descrição: dc.descriptionUma coloração de arestas própria de um grafo é uma atribuição de cores para as suas arestas tal que arestas incidentes em um mesmo vértice têm cores distintas. O Problema da Coloração de Arestas é responder, dado um grafo, qual o menor número de cores para uma coloração de arestas própria. Esse número é chamado de índice cromático e, para um grafo 𝐺, é denotado por 𝜒′(𝐺). Por definição, o índice cromático é pelo menos ∆(𝐺), onde ∆(𝐺) é o maior número de arestas incidentes em um mesmo vértice do grafo 𝐺. Em 1964, Vizing provou que 𝜒′(𝐺) ≤ ∆(𝐺) + 1 para qualquer grafo simples 𝐺. Portanto, quando 𝐺 é simples, ∆(𝐺) ≤ 𝜒′(𝐺) ≤ ∆(𝐺) + 1. Um grafo é Classe 1 se o seu índice cromático é igual ao seu grau máximo, e é Classe 2 caso contrário. O Problema da Classificação é decidir se um grafo simples é Classe 1. A despeito de haver apenas dois possíveis valores para o índice cromático de um grafo simples, o Problema da Classificação é NP-completo. Em 1985, em sua famosa coluna "The NP-Completeness Column: an Ongoing Guide”, David Johnson classificou alguns problemas da Teoria dos Grafos em relação à sua complexidade computacional. Em alguns casos, esta complexidade ainda era desconhecida e Johnson identificou classes de grafos para as quais considerou que seria fácil determiná-la. Nas classes de grafos split, de comparabilidade e de intervalos, por exemplo, Johnson considerou que determinar a complexidade computacional do Problema da Classificação era possivelmente fácil. Entretanto, após 35 anos, apenas a complexidade computacional do Problema da Classificação para os grafos de comparabilidade foi determinada, sendo este um problema NP-completo. Esta dissertação apresenta uma solução de tempo polinomial para o Problema da Classificação para grafos split-intervalos, além de identificar e corrigir um problema na prova que determina o índice cromático dos grafos split-comparabilidade.-
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.publisherPrograma de Pós-Graduação em Ciência da Computação-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightsAttribution-NonCommercial-ShareAlike 4.0 International-
Direitos: dc.rightshttp://creativecommons.org/licenses/by-nc-sa/4.0/-
Palavras-chave: dc.subjectRepresentações dos grafos-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectCores-
Palavras-chave: dc.subjectAlgorítmos computacionais-
Palavras-chave: dc.subjectRepresentations of graphs-
Palavras-chave: dc.subjectGraph theory-
Palavras-chave: dc.subjectColors-
Palavras-chave: dc.subjectComputer algorithms-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Palavras-chave: dc.subjectEngenharia/Tecnologia/Gestão-
Título: dc.titleColoração de arestas em grafos split-comparabilidade e split-intervalos-
Título: dc.titleEdge coloring in split-comparability and split-interval graphs-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.