Please use this identifier to cite or link to this item:
https://rd.uffs.edu.br/handle/prefix/3607
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor1 | Zatesko, Leandro Miranda | - |
dc.creator | Zorzi, Alesom | - |
dc.date | 2016 | - |
dc.date.accessioned | 2020-03-02T15:59:11Z | - |
dc.date.available | 2020 | - |
dc.date.available | 2020-03-02T15:59:11Z | - |
dc.date.issued | 2016 | - |
dc.identifier.uri | https://rd.uffs.edu.br/handle/prefix/3607 | - |
dc.description.abstract | The Classification Problem, which consists of finding the minimum number of colors in order to color every edge of a graph so that no adjacent edges receive the same color, is an NP-complete problem, although we have only two possibilities for that number, by Vizing’s Theorem. For specific classes of graphs, polynomial time algorithms have already been found. The class of the join graphs, a significantly populous class of graphs — it is a superclass of the cographs, complete graphs (Kn) and the complete multipartite graphs— does not have a polynomial-time algorithm for the Classification Problem. However, the overfull conjecture and a linear-time algorithm for recognizing overfull-subgraph graphs give us some evidences for the existence of a polynomial-time algorithm for the Classification Problem. Therefore, this work presents a study about the Classification Problem, aiming to propose some new results so that the state of the art can be improved. | pt_BR |
dc.description.resumo | O Problema da Classificação de Grafos, que consiste em encontrar o número mínimo de cores necessárias para colorir todas as arestas de um grafo de modo que arestas incidentes ao mesmo vértice recebam cores distintas, é um problema NP-completo, ainda que existam apenas duas possibilidades para tal número, conforme o Teorema de Vizing. Para algumas classes específicas de grafos já foram encontrados algoritmos de tempo polinomial para o problema referido. A classe dos grafos-junção, uma classe consideravelmente populosa de grafos — classe esta que é superclasse dos cografos conexos, dos grafos completos (Kn) e dos grafos multipartidos completos — ainda não possui algoritmo de tempo polinomial para o Problema da Classificação. Contudo, a Conjectura Overfull e um algoritmo de tempo linear para o reconhecimento de grafos que são subgrafo-overfull nos dão indicativos de que tal classe possui algoritmo de tempo polinomial para o Problema da Classificação de Grafos. Sendo assim, o presente trabalho apresenta um estudo sobre o Problema da Classificação de Grafos e da classe dos grafos-junção, com o objetivo de propor novos resultados para que o estado da arte do problema possa ser avançado. | pt_BR |
dc.description.provenance | Submitted by Franciele Scaglioni da Cruz (franciele.cruz@uffs.edu.br) on 2020-02-27T13:26:51Z No. of bitstreams: 1 ZORZI.pdf: 1514773 bytes, checksum: 26dc4501adc088a98836b8e3a87a0235 (MD5) | en |
dc.description.provenance | Approved for entry into archive by Franciele Scaglioni da Cruz (franciele.cruz@uffs.edu.br) on 2020-03-02T15:59:11Z (GMT) No. of bitstreams: 1 ZORZI.pdf: 1514773 bytes, checksum: 26dc4501adc088a98836b8e3a87a0235 (MD5) | en |
dc.description.provenance | Made available in DSpace on 2020-03-02T15:59:11Z (GMT). No. of bitstreams: 1 ZORZI.pdf: 1514773 bytes, checksum: 26dc4501adc088a98836b8e3a87a0235 (MD5) Previous issue date: 2016 | en |
dc.language | por | pt_BR |
dc.publisher | Universidade Federal da Fronteira Sul | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.department | Campus Chapecó | pt_BR |
dc.publisher.initials | UFFS | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Ciência da computação | pt_BR |
dc.subject | Matemática da computação | pt_BR |
dc.subject | Teoria dos grafos | pt_BR |
dc.subject | Grafos aleatórios | pt_BR |
dc.title | Classificação de grafos-junção quanto ao índice cromático | pt_BR |
dc.type | Monografia | pt_BR |
Appears in Collections: | Ciência da Computação |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.