Problema do empacotamento aberto em classes de grafos
| dc.creator | Sarah Rebecca Dias Luiz | |
| dc.date.accessioned | 2026-02-13T17:01:12Z | |
| dc.date.issued | 2023-10-17 | |
| dc.description.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. | |
| dc.description.sponsorship | CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico | |
| dc.identifier.uri | https://hdl.handle.net/1843/1653 | |
| dc.language | por | |
| dc.publisher | Universidade Federal de Minas Gerais | |
| dc.rights | Acesso aberto | |
| dc.subject | Computação – Teses | |
| dc.subject | Teoria dos grafos – Teses | |
| dc.subject | Complexidade Computacional – Teses | |
| dc.subject | Empacotamento e cobertura combinatória - Teses | |
| dc.subject.other | Grafo | |
| dc.subject.other | Classes de grafos | |
| dc.subject.other | Complexidade computacional | |
| dc.subject.other | Dominação | |
| dc.subject.other | Empacotamento | |
| dc.title | Problema do empacotamento aberto em classes de grafos | |
| dc.title.alternative | Open packing problem in graph glasses | |
| dc.type | Dissertação de mestrado | |
| local.contributor.advisor1 | Vinícius Fernandes dos Santos | |
| local.contributor.advisor1Lattes | http://lattes.cnpq.br/6270626469557436 | |
| local.contributor.referee1 | Guilherme de Castro Mendes Gomes | |
| local.contributor.referee1 | Ana Karolinna Maia de Oliveira | |
| local.creator.Lattes | http://lattes.cnpq.br/3621837804543598 | |
| local.description.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. | |
| local.publisher.country | Brasil | |
| local.publisher.department | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO | |
| local.publisher.initials | UFMG | |
| local.publisher.program | Programa de Pós-Graduação em Ciência da Computação | |
| local.subject.cnpq | CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO |