Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Finura em Grafos Cordais
View through CrossRef
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álogo, a finura cordal, apresentando limites superiores e resultados parciais a respeito de sua complexidade computacional. Além disso, também determinamos a complexidade de problemas clássicos em grafos de finura cordal limitada. Em particular, mostramos que CONJUNTO INDEPENDENTE permanece NP-Difícil mesmo em grafos de finura cordal 3. Por outro lado, mostramos que é possível generalizar o resultado de polinomialidade de CLIQUE em grafos cordais para grafos de finura cordal 2.
Sociedade Brasileira de Computação - SBC
Title: Finura em Grafos Cordais
Description:
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álogo, a finura cordal, apresentando limites superiores e resultados parciais a respeito de sua complexidade computacional.
Além disso, também determinamos a complexidade de problemas clássicos em grafos de finura cordal limitada.
Em particular, mostramos que CONJUNTO INDEPENDENTE permanece NP-Difícil mesmo em grafos de finura cordal 3.
Por outro lado, mostramos que é possível generalizar o resultado de polinomialidade de CLIQUE em grafos cordais para grafos de finura cordal 2.
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 ...
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...
Coloração equilibrada de grafos n-Star-Clique
Coloração equilibrada de grafos n-Star-Clique
Nesse artigo investigamos o problema de coloração equilibrada para grafos unipolares, uma superclasse de grafos split. Em particular, apresentamos um algoritmo baseado em fluxo máx...
Sobre grafos cubridores de los grafos de comparabilidad
Sobre grafos cubridores de los grafos de comparabilidad
Un grafo es de comparabilidad si es posible orientar sus aristas en forma transitiva. Las primeras preguntas que surgen naturalmente son: el problema del reconocimiento, dado un gr...
Predicting Properties of Polymer Materials Using Machine Learning Methods
Predicting Properties of Polymer Materials Using Machine Learning Methods
Accurate prediction of polymer properties is essential for their effective application and devel- opment. However, traditional experimental methods are often prohibitively time-con...
Aspectos de complexidade parametrizada e problemas análogos em problemas de lista coloração de grafos e suas variações
Aspectos de complexidade parametrizada e problemas análogos em problemas de lista coloração de grafos e suas variações
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 red...
Propagação epidêmica em multigrafos
Propagação epidêmica em multigrafos
Multigrafos são redes que possuem múltiplas conexões entre vértices. Redes com distri- buição de grau em lei de potência P (k) ∼ k −γ apresentam um corte natural kN ∼ N γ−1 . Probl...