Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Almeida, Sheila Morais de | - |
Autor(es): dc.contributor | Almeida, Sheila Morais de | - |
Autor(es): dc.contributor | Queiroz, Saulo Jorge Beltrão de | - |
Autor(es): dc.contributor | Matos, Simone Nasser | - |
Autor(es): dc.creator | Castro, Luis Angelo Loss de | - |
Data de aceite: dc.date.accessioned | 2022-02-21T21:49:11Z | - |
Data de disponibilização: dc.date.available | 2022-02-21T21:49:11Z | - |
Data de envio: dc.date.issued | 2020-11-18 | - |
Data de envio: dc.date.issued | 2020-11-18 | - |
Data de envio: dc.date.issued | 2018-06-13 | - |
Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/15966 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/661261 | - |
Descrição: dc.description | A characterization of a graph class is the determination of structural properties that uniquely identify the graphs in this class. Those characterizations can give important information that supports many combinatorial problems, such as the Edge Coloring Problem. An edge coloring of a graph G is an assigment of colors to the edges of G such that the colors of any two edges that share a common vertex are distinct. The Edge Coloring Problem is to determine the minimum number of colors that allows an edge coloring for a given graph G. It is known that any simple graph G has an edge coloring with (G)+1 colors, where (G) is the maximum degree of G. However, some graphs G have an edge coloring with (G) colors. It is an NP-complete problem to decide if a graph G has an edge coloring with (G) colors. This work shows new characterizations for split-co-comparability graphs. Using these characterizations, it is determined a subset of split-co-comparability graphs for which the decision version of the Edge Coloring Problem has polynomial time solution. | - |
Descrição: dc.description | Uma caracterização de um conjunto de grafos é a determinação de propriedades estruturais que identifiquem unicamente os grafos desse conjunto. Essas caracterizações podem dar informações importantes que auxiliam na solução de diversos problemas combinatoriais, como por exemplo, o Problema da Coloração de Arestas. Uma coloração de arestas em um grafo G é uma atribuição de cores para as arestas de G de forma que as cores de quaisquer duas arestas que incidem no mesmo vértice são distintas. O Problema da Coloração de Arestas é determinar o menor número de cores que permite uma coloração de arestas para um dado grafo G. Sabe-se que qualquer grafo simples G tem uma coloração de arestas com _(G) + 1 cores, onde _(G) é o grau máximo do grafo G. Entretanto, alguns grafos G têm uma coloração de arestas com _(G) cores. Decidir se um grafo G tem uma coloração de arestas com _(G) cores é um problema NP completo. Este trabalho apresenta novas caracterizações para os grafos split-co comparabilidade. Usando essas caracterizações, determina-se um subconjunto dos grafos split-co comparabilidade para o qual a versão de decisão do Problema da Coloração de Arestas tem solução em tempo polinomial. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Universidade Tecnológica Federal do Paraná | - |
Publicador: dc.publisher | Ponta Grossa | - |
Publicador: dc.publisher | Brasil | - |
Publicador: dc.publisher | Departamento Acadêmico de Informática | - |
Publicador: dc.publisher | Ciência da Computação | - |
Publicador: dc.publisher | UTFPR | - |
Direitos: dc.rights | openAccess | - |
Palavras-chave: dc.subject | Representações dos grafos | - |
Palavras-chave: dc.subject | Solução de problemas | - |
Palavras-chave: dc.subject | Polinômios | - |
Palavras-chave: dc.subject | Representations of graphs | - |
Palavras-chave: dc.subject | Problem solving | - |
Palavras-chave: dc.subject | Polynomials | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | - |
Título: dc.title | Caracterização e coloração de arestas em grafos split-co-comparabilidade | - |
Título: dc.title | Characterization and edge coloring on split-co-comparability graphs | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositorio Institucional da UTFPR - RIUT |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: