Conjunto Independente e Cobertura por Cliques em Grafos de Disco Unitário e Moeda Unitária
Autores
|
2291 |
416,410,979
|
|
|
2292 |
416,410,979
|
|
|
2293 |
416,410,979
|
Informações:
Publicações do PESC
Este trabalho descreve um estudo dos problemas de encontrar um conjunto independente máximo e uma cobertura por cliques mínima em grafos de disco unitário e de moeda unitária. Um grafo é de disco unitário quando seus vértices estão associados a discos no plano de mesmo diâmetro e existe aresta entre dois deles se houver interseção entre os respectivos discos. Quando os discos não podem se sobrepor, temos a subclasse dos grafos de moeda unitária.
Os principais resultados dessa tese são o estabelecimento da complexidade dos problemas citados para a classe dos grafos de moeda unitária, ambos NP-completos, e dois algoritmos aproximativos. Um algoritmo para o problema da cobertura por cliques em grafos de moeda unitária, e um algoritmo para o problema da cobertura por cliques em grafos de disco unitário.
This work describes a study on the maximum independent set problem and the minimum partition into cliques problem in unit disk graphs and penny graphs. A graph is a unit disk graph if its vertices are associated to discs on the plane with the same diameter and there is an edge between two of them if and only if the corresponding discs intersect. When the disks are not allowed to overlap each other, we have the class of penny graphs.
The main results of this thesis are the establishment of the complexity of the above problems, both NP-complete, and two approximation algorithms. An algorithm to find a minimum clique cover in penny graphs and an algorithm to find a minimum clique cover in unit disk graphs.