Coloraaao De Vartices
Mostrando 1-5 de 5 artigos, teses e dissertações.
-
1. GeraÃÃo de Facetas para Politopos de Conjuntos Independentes / Facet-generating Procedures for Stable Set Polytopes
Um conjunto independente de um grafo à um subconjunto de vÃrtices que nÃo contÃm nenhum par de vÃrtices vizinhos. O problema do maior conjunto independente consiste em encontrar um conjunto independente de cardinalidade mÃxima. O problema do maior subgrafo induzido k-partido consiste em encontrar k conjuntos independentes cuja uniÃo tenha cardinalidad
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia. Publicado em: 26/09/2011
-
2. Estudo de casos de complexidade de coloraÃÃes gulosa de vÃrtices e de arestas / Case studies of complexity of greedy colorings of vertices and edges
Os problemas de colorac Ëao de vÂertices e de arestas, que consistem em determinar o menor nÂumero de cores necessÂarias para colorir os vÂertices e arestas de um grafo, respectivamente, de forma que vÂertices adjacentes e arestas adjacentes, respectivamente, possuem cores distintas, sËao problemas computacionalmente difÂıceis e sËao objeto d
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia. Publicado em: 07/04/2011
-
3. Limites inferiores para o problema de coloraÃÃo de vÃrtices via geraÃÃo de cortes e colunas / Inferior limits for the problem of vertex coloring saw generation of cuts and columns
Neste trabalho abordamos o problema de coloraÃÃo de vÃrtices via programaÃÃo inteira. Uma versÃo expandida da formulaÃÃo por conjuntos independentes à utilizada para abrigar outras sub-estruturas do grafos alÃm dos vÃrtices. Cada uma dessas sub-estruturas define uma restriÃÃo que determina quantos conjuntos independentes sÃo necessarios para co
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia. Publicado em: 22/11/2008
-
4. Um estudo computacional sobre o problema de decomposiÃÃo de grafos em Ãrvore / A computational study of the tree decomposition problem
A noÃÃo de DecomposiÃÃo em Ãrvore foi introduzida por Robertson e Seymour em sua sÃrie de artigos sobre menores de grafos e pode ser definida, intuitivamente, como uma organizaÃÃo dos vÃrtices e arestas do grafo em uma estrutura de Ãrvore, sendo a largura da decomposiÃÃo igual ao tamanho do maior subconjunto de vÃrtices relacionado a um nà dest
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia. Publicado em: 31/08/2005
-
5. A study on the polytope and lower bounds of the representatives coloring formulation / Um estudo do politopo e dos limites inferiores gerados pela formulaÃÃo de coloraÃÃo dos representantes
O problema de coloraÃÃo de vÃrtices à considerado um dos modelos mais estudados em teoria dos grafos pela sua relevÃncia em campos prÃticos e teÃricos. Do ponto de vista teÃrico, o problema de coloraÃÃo à NP - DifÃcil. AlÃm disto, foi classificado entre os problemas mais difÃceis de NP, no sentido de que achar uma aproximaÃÃo para o nÃmero c
Publicado em: 2005