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...
ANÁLISE DE ILHAS EM REDES SEMÂNTICAS BASEADAS EM LIVROS DIDÁTICOS
ANÁLISE DE ILHAS EM REDES SEMÂNTICAS BASEADAS EM LIVROS DIDÁTICOS
A Ciência das Redes é um campo interdisciplinar que investiga padrões nas relações em sistemas baseados em grafos. O estudo de ilhas em redes possibilita a identificação das relaçõ...
Interações entre pré-escolares: possibilidades de análises
Interações entre pré-escolares: possibilidades de análises
Buscou-se, neste trabalho, construir a rede de relações sociais entre pré-escolares e analisar a pertinência das metodologias utilizadas para a coleta e análise dos dados. Particip...