Problema do empacotamento aberto em classes de grafos
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Open packing problem in graph glasses
Primeiro orientador
Membros da banca
Guilherme de Castro Mendes Gomes
Ana Karolinna Maia de Oliveira
Ana Karolinna Maia de Oliveira
Resumo
Problemas de dominação em grafos estão entre os mais clássicos problemas dentro da área de Teoria de Grafos e são amplamente estudados. Uma variação importante do problema de dominação é o Problema de Dominação Total em Grafos, que consiste em saber se um grafo G tem um subconjunto de vértices de tamanho k que faz vizinhança com todos os demais
vértices do grafo, incluindo os próprios vértices do subconjunto. O Problema de Empacotamento Aberto em Grafos é o problema dual da dominação total de um ponto de vista da programação inteira. Esse problema consiste em saber se um grafo G possui um subconjunto de vértices de tamanho k cuja vizinhança aberta, par a par, não tenha interseção. Embora importante, o Problema de Empacotamento Aberto em Grafos segue em aberto em diversas classes de grafos, isto é, segue sem classificação de dificuldade. Esse trabalho, então, busca estudar a complexidade computacional desse problema para algumas classes de grafos, assim como busca limitantes superiores para outras. Em particular, encontramos algoritmos que calculam o tamanho do maior empacotamento aberto de grafos de intervalo e de grafos de largura arb´orea limitada em tempo polinomial. Além disso, encontramos limites superiores para o tamanho de empacotamentos abertos em grafos com diâmetro igual a dois e para grafos que não possuam K5 como menor.
Abstract
Domination problems in graphs are among the most classic problems in the field of Graph Theory and are widely studied. An important variation of the domination problem is the Total Domination Problem in Graphs, which consists of knowing if a graph G has a subset of vertices of size k that is neighbor to all the other vertices of the graph, including the vertices in the subset itself. The Open Packing Problem in Graphs is the dual object of total domination from an integer programming point of view. This problem consists of knowing whether a graph G has a subset of vertices of size k whose each pair of open neighborhoods have no intersection. Although important, the Open Packing Problem in Graphs remains open for several graph classes, which means it does not have its difficulty classified. This work seeks to study the computational complexity of this problem for some classes of graphs, as well as search for upper bounds for others. In particular, we found algorithms that compute the size of the largest open packing of interval and partial k-tree graphs in polynomial time. Furthermore, we found upper bounds for the size of open packings in graphs with a diameter equal to two and for graphs that do not have K5 as a minor.
Assunto
Computação – Teses, Teoria dos grafos – Teses, Complexidade Computacional – Teses, Empacotamento e cobertura combinatória - Teses
Palavras-chave
Grafo, Classes de grafos, Complexidade computacional, Dominação, Empacotamento