Problemas de particionamento de grafos em árvores monocromáticas
Carregando...
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
Graph partitioning problems in monochromatic trees
Primeiro orientador
Membros da banca
Guilherme Oliveira Mota
Júlio César Silva Araújo
Júlio César Silva Araújo
Resumo
Neste trabalho, estudamos o problema de Partição de Grafos em Árvores Monocromáticas (PGMT). Neste problema, é dado um grafo G, com n vértices, que está colorido nas arestas, e o objetivo é encontrar o menor número de árvores monocromáticas disjuntas nos vértices que cobrem todos os vértices de G. Primeiramente, estudamos a complexidade computacional desse problema, sobre a qual demonstramos que o PGMT é NP-completo quando consideramos alguns parâmetros como: frequência de cores, grau máximo e número de cores; ou quando restringimos à classe dos grafos bipartidos completos onde o número de árvores é limitado. Também demonstramos um limitante inferior para a execução de algoritmos exatos usando a Hipótese do Tempo Exponencial (ETH). Mais
precisamente, demonstramos que existe δ > 0 tal que PGMT não pode ser resolvido em tempo O(2^δn), a menos que a ETH seja falsa. Como resultados positivos, apresentamos um algoritmo de complexidade O(n^2) quando G é uma árvore e apresentamos também um algoritmo parametrizado pelo número de cores r e pela largura arbórea t do grafo da entrada que executa em tempo O(n^O(1)(r · t)^(2t+1)).
Abstract
In this work, we study the Partitioning Graphs into Monochromatic Trees (PGMT) problem. In this problem, an edge-coloured graph G with n vertices is given, and the goal is to find the smallest number of vertex disjoint monochromatic trees that cover all the
vertices of G. First, we study the computational complexity of this problem, in which we show that the PGMT is NP-complete when we consider some parameters such as: color frequency, maximum degree and number of colors; or when we restrict to the class of complete bipartite graphs where the number of trees is limited. We also show a lower bound for executing exact algorithms using the Exponential Time Hypothesis (ETH). More precisely, we show that there is δ > 0 such that PGMT cannot be resolved in time
O(2δn), unless a ETH is false. As positive results, we present an algorithm of complexity O(n 2 ) when G is a tree and we also present an algorithm parameterized by the number of colors r and by the treewidth t of the input graph that runs in time O(n O(1)(r · t) 2t+1).
Assunto
Computação – Teses, Algoritmos de computador – Teses, Complexidade computacional – Teses, Árvores (Teoria dos grafos) - Teses
Palavras-chave
Algoritmos, Árvores monocromáticas, Complexidade parametrizada, Grafos
Citação
Departamento
Endereço externo
Avaliação
Revisão
Suplementado Por
Referenciado Por
Licença Creative Commons
Exceto quando indicado de outra forma, a licença deste item é descrita como Acesso Aberto