Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Aspectos de complexidade parametrizada e problemas análogos em problemas de lista coloração de grafos e suas variações
View through CrossRef
Lista-coloração é uma generalização do problema clássico de coloração de vértices em grafos. Tal problema possui algumas variações, dentre elas a coloração. Neste trabalho, uma redutibilidade do problema da lista coloração para a coloração e pré-coloração estendida é apresentada, para melhor se prover uma análise da coloração sob o enfoque da complexidade parametrizada, onde a mesma é FPT quando parametrizada pela cobertura de vértices e listas de cores. É apresentada também a prova de corretude de um algoritmo polinomial, dado na literatura, para coloração em grafos bipartidos completos.
Sociedade Brasileira de Computação - SBC
Title: Aspectos de complexidade parametrizada e problemas análogos em problemas de lista coloração de grafos e suas variações
Description:
Lista-coloração é uma generalização do problema clássico de coloração de vértices em grafos.
Tal problema possui algumas variações, dentre elas a coloração.
Neste trabalho, uma redutibilidade do problema da lista coloração para a coloração e pré-coloração estendida é apresentada, para melhor se prover uma análise da coloração sob o enfoque da complexidade parametrizada, onde a mesma é FPT quando parametrizada pela cobertura de vértices e listas de cores.
É apresentada também a prova de corretude de um algoritmo polinomial, dado na literatura, para coloração em grafos bipartidos completos.
Related Results
Sobre los grafos VPT y los grafos EPT
Sobre los grafos VPT y los grafos EPT
El grafo de intersección de una familia de conjuntos es un grafo cuyos vértices son los miembros de la familia y la adyacencia es definida por la intersección no vacía de los corre...
Sobre grafos clique críticos
Sobre grafos clique críticos
Se llama completo de un grafo a un conjunto de vértices adyacentes entre si; si un completo es maximal con respecto a la inclusión, se dice que es un clique del grafo. Los cliques ...
Un estudio conjunto de grafos cordales y dualmente cordales
Un estudio conjunto de grafos cordales y dualmente cordales
Los grafos cordales fueron definidos originalmente como aquellos grafos para los cuales todo ciclo de longitud mayor o igual que cuatro posee una cuerda. Los gafos cordales han sid...
Causal discovery and prediction: methods and algorithms
Causal discovery and prediction: methods and algorithms
(English) This thesis focuses on the discovery of causal relations and on the prediction of causal effects. Regarding causal discovery, this thesis introduces a novel and generic m...
Internações no SUS por Condições Sensíveis à Atenção Primária no Paraná antes e durante a pandemia de COVID-19
Internações no SUS por Condições Sensíveis à Atenção Primária no Paraná antes e durante a pandemia de COVID-19
Estudo descritivo, que objetivou analisar internações hospitalares por condições sensíveis à APS no biênio pré-pandêmico (2018 - 2019) e no primeiro biênio da pandemia de Covid-19 ...
Finura em Grafos Cordais
Finura em Grafos Cordais
A finura de um grafo é uma medida do "quão distante" um grafo está de um grafo de intervalo, sendo estes exatamente os grafos de finura 1. Neste artigo introduzimos um conceito aná...
La Lista Roja de Hispania Nostra
La Lista Roja de Hispania Nostra
La Lista Roja es una forma de participación social mediante la utilización de las tecnologías de la información y la comunicación para la conservación del patrimonio cultural. La i...
Filling more gaps on the edge-coloring problem of split graphs
Filling more gaps on the edge-coloring problem of split graphs
O problema da coloração de arestas é provado ser NP-completo no caso geral. Entretanto, para diversas classes de grafos, este problema permanece em aberto. Uma destas classes é a c...