Search

Seja G = (V (G), E (G)) um grafo. Um conjunto I ⊆V (G) é independente quando quaisquer pares de vértices pertencentes a I não são adjacentes em G. Um conjunto independente é dito maximal se não está propriamente contido em nenhum outro conjunto independente de G. Um grafo G é bem-coberto se todo conjunto independente maximal de G é máximo. Determinar se um grafo é bem-coberto é um problema coNP-completo. Nós apresentamos um algoritmo de kernelização para o problema de determinar a BEM-COBERTURA para grafos distância para uma classe Q. Também resultados relacionados a intratabilidade da BEM-COBERTURA parametrizado para distância de grafos livres de Cl com l ≥5. E por fim a inexistência de um kernel polinomial para BEM-COBERTURA parametrizado por distância para cluster Let G = (V (G), E (G)) be a graph. A set I ⊆ V (G) is independent when any pairs of vertices belonging to I are not adjacent in G. An independent set is maximal if it is not properly contained in any other independent set of G. A graph G is well-covered if every maximal independent set of G is maximum. Determining whether a graph is well-covered is a coNP-complete problem. We present a kernelization algorithm for the problem of determining the WELL-COVERAGE for distance graphs for a class Q. Also results related to the intractability of WELL-COVERAGE parameterized for distance of free graphs of Cl with l ≥5. And finally, the inexistence of a polynomial kernel for WELL-COVERAGE parameterized by distance for cluster. Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES

EPG é um grafo de aresta-interseção de caminhos sobre uma grade. Nesta tese de doutorado exploraremos principalmente os grafos EPG, em particular os grafos B1-EPG. Entretanto, outras classes de grafos de interseção serão estu dadas, como as classes de grafos VPG, EPT e VPT, além dos parâmetros número de Helly e número de Helly forte nos grafos EPG e VPG. Apresentaremos uma prova de NP-completude para o problema de reconhecimento de grafos B1-EPG Helly. Investigamos os parâmetros número de Helly e o número de Helly forte nessas duas classes de grafos, EPG e VPG, a fim de determinar limites inferiores e superi ores para esses parâmetros. Resolvemos completamente o problema de determinar o número de Helly e o número de Helly forte para os grafos Bk-EPG e Bk-VPG, para cada valor k. Em seguida, apresentamos o resultado de que todo grafo B1-EPG Chordal está simultaneamente nas classes de grafos VPT e EPT. Em particular, descrevemos estruturas que ocorrem em grafos B1-EPG que não suportam uma representação B1-EPG-Helly e assim definimos alguns conjuntos de subgrafos que delimitam sub famílias Helly. Além disso, também são apresentadas características de algumas famílias de grafos não triviais que estão propriamente contidas em B1-EPG-Helly An EPG graph G is an edge-intersection graph of paths on a grid. In this doctoral thesis we will mainly explore the EPG graphs, in particular B1-EPG graphs. However, other classes of intersection graphs will be studied such as VPG, EPT and VPT graph classes, in addition to the parameters Helly number and strong Helly number to EPG and VPG graphs. We will present the proof of NP-completeness to Helly-B1-EPG graph recognition problem. We investigate the parameters Helly number and the strong Helly number in both graph classes, EPG and VPG in order to determine lower bounds and upper bounds for this parameters. We completely solve the problem of determining the Helly and strong Helly numbers, for Bk-EPG, and Bk-VPG graphs, for each value k. Next, we present the result that every Chordal B1-EPG graph is simultaneously in the VPT and EPT graph classes. In particular, we describe structures that occur in B1-EPG graphs that do not support a Helly-B1-EPG representation and thus we define some sets of subgraphs that delimit Helly subfamilies. In addition, features of some non-trivial graph families that are properly contained in Helly-B1 EPG are also presented.

Submitted by Paloma Arruda (palomaoliiveira75@gmail.com) on 2021-02-22T04:48:48Z No. of bitstreams: 1 SancreyRodriguesAlves.pdf: 3549907 bytes, checksum: 36e0d743defbece27b8b9fc24e8e7f37 (MD5) Approved for entry into archive by Moreno Barros (moreno@ct.ufrj.br) on 2021-04-05T02:16:07Z (GMT) No. of bitstreams: 1 SancreyRodriguesAlves.pdf: 3549907 bytes, checksum: 36e0d743defbece27b8b9fc24e8e7f37 (MD5) Made available in DSpace on 2021-04-05T02:16:07Z (GMT). No. of bitstreams: 1 SancreyRodriguesAlves.pdf: 3549907 bytes, checksum: 36e0d743defbece27b8b9fc24e8e7f37 (MD5) Previous issue date: 2019-12 [PT] Uma partição-(r,l) de um grafo G é uma partição do seu conjunto de vértices em r conjuntos independentes e ` cliques. Um grafo é chamado de grafo-(r,l) se admite uma partição-(r,l). Um grafo é bem coberto se todo conjunto independente maximal é máximo. Um grafo é um grafo bem coberto-(r,l) se é, ao mesmo tempo, (r,l) e bem coberto. Neste trabalho consideramos dois tipos de problemas de decisão distintos. No problema grafos bem cobertos-(r,l) (abreviadamente gbc(r,l)), o grafo G é dado, e quer-se decidir se o grafo G é um grafo-(r,l) bem coberto. No problema grafos-(r,l) bem cobertos (abreviadamente g(r,l) bc) é dado um grafo-(r,l) como entrada juntamente com uma partição de V (G) em r conjuntos independentes e cliques, e a pergunta é se G é bem coberto. No contexto dos problemas sanduíche, consideramos a classe dos grafos bem cobertos-(r,l) que são reconhecidos em tempo polinomial, a saber: (0, 1), (1, 0), (0, 2), (2, 0), (1, 1) e (1, 2). Resolvemos este problema para cinco das seis classes, e o problema permanece em aberto apenas quando (r,l) = (2, 0). Também apresentamos, neste trabalho, a solução do problema probe particionado para grafos bem cobertos-(r,l) para todas as classes de grafos bem cobertos- (r,l) que são reconhecíveis em tempo polinomial, com exceção das classes (2, 0) e (1, 2). Além disso, consideramos a complexidade parametrizada do problema grafo bem coberto, com ênfase especial no caso em que o grafo dado é um grafo-(r,l), para algumas escolhas de parâmetros, tais como o tamanho α de um conjunto independente maximal do grafo de entrada, diversidade de vizinhança, e o número de cliques em uma partição-(r,l). i [EN] A (r,l)-partition of a graph G is a partition of its vertex set into r independent sets and cliques. A graph is a (r,l)-graph if it admits a (r,l)-partition. A graph is a (r,l) -graph if it admits a (r,l)-partition. A graph is well-covered when each maximal independent set is maximum. A graph is a (r, l)-well-covered graph if it is (r,l) and well-covered, simultaneously. In this work we consider two different decision problems. In the (r,l)-well-covered graph problem (gbc(r,l) for short), a graph G is provided as input, and the question is whether G is an (r,l)- well-covered graph. In the well-covered (r,l)-graph problem (g(r,l )bc for short), a (r,l)-graph G together with an (r,l)-partition of V (G) into r independent sets and cliques are provided as input, and the question is whether G is wellcovered. In the context of sandwich problems, we consider the classes (r,l)-well-covered which are recognized in polynomial time, namely: (0, 1), (1, 0), (0, 2), (2, 0), (1, 1), and (1, 2). We solved this problem for five of those six classes, and the problem remains open only when (r,l) = (2, 0). We also present, in this work, the solution of partitioned probe for (r,l)-wellcovered graphs problem for all graph classes well covered-(r,l) which are recognizable in polynomial time, except for the classes (2, 0) and (1, 2). In addition, we consider the parameterized complexity of well-covered graph problem with special emphasis on the case where the given graph is a (r,l)-graph for several choices of parameters, such as the size α of a maximal independent set of the input graph, neighborhood diversity, and the number of cliques in an (r,l)-partition.

Submitted by Boris Flegr (boris@uerj.br) on 2021-01-05T17:53:34Z No. of bitstreams: 1 Bruno_CComp_final.pdf: 1852430 bytes, checksum: 74dda30b4b5ed9d604efff2d7a5118d4 (MD5) Made available in DSpace on 2021-01-05T17:53:34Z (GMT). No. of bitstreams: 1 Bruno_CComp_final.pdf: 1852430 bytes, checksum: 74dda30b4b5ed9d604efff2d7a5118d4 (MD5) Previous issue date: 2019-03-13 Graph matchings are problems that have been studied for a long time and which bring great contributions to Graph Theory from both the theoretical and practical points of view. As a tradition, there are numerous studies in this field for unrestricted and unweightedmatchings. Morerecently, subgraph-restrictedmatchingshavebeenproposed, which consider properties from the subgraph induced by the matching vertices. In this paper, we approach one of these new proposals, which are disconnected matchings, which seekstostudymatchingsanditscardinalities,suchthatthesubgraphinducedbymatching vertices is disconnected. We were able to solve the problem for simple classes of graphs like paths, cycles and complete. In addition, we obtained results for split graphs, trees, block graphs and chordal graphs. For these last three classes, we present a theoretical basis that includes theorems of characterizations, as well as three new algorithms. This paper also includes a fourth algorithm, which finds a maximum matching for block graphs in linear time A determinação de emparelhamentos máximos em grafos corresponde a problemas há muito tempo estudados e que trazem grandes contribuições à Teoria de Grafos, tanto do ponto de vista teórico quanto prático. Como tradição, há numerosos estudos na área destinados a emparelhamentos irrestritos e sem pesos. Mais recentemente, foram propostos os emparelhamentos restritos a subgrafos, que consideram propriedades dos subgrafos induzidos pelos vértices do emparelhamento. Neste trabalho, abordamos uma dessas novas propostas, que são os emparelhamentos desconexos, os quais procuram estudar emparelhamentos tais que os subgrafos induzidos pelos vértices dos emparelhamentos sejam desconexos. Conseguimos resolver o problema para classes simples de grafos tais como caminhos, ciclos, completos. Além disso, também obtivemos resultados para grafos split, árvores, grafos bloco e grafos cordais. Para essas três últimas classes, apresentamos uma base teórica que inclui teoremas de caracterizações, assim como três novos algoritmos. O trabalho também inclui um quarto algoritmo que determina um emparelhamento máximo para grafos bloco em tempo linear

Submitted by Boris Flegr (boris@uerj.br) on 2021-01-05T17:53:28Z No. of bitstreams: 1 RodolfoVersaoBDTD2018.pdf: 5703653 bytes, checksum: 80064384ac2fb935a383a297ac8b3752 (MD5) Made available in DSpace on 2021-01-05T17:53:28Z (GMT). No. of bitstreams: 1 RodolfoVersaoBDTD2018.pdf: 5703653 bytes, checksum: 80064384ac2fb935a383a297ac8b3752 (MD5) Previous issue date: 2018-10-09 Optimization problems have big importance in the industry field, from production management to production outflow and product transportation. Many problems of interest are classified as NP-Hard, so there is no known algorithm to find the exact solution in a polinomial time. Therefore heuristic strategies with the ability to escape from poor quality local optima (meta-heuristics) are generally employed. In general, the local search is the most costly, in computational time, phase of a meta-heuristic, becoming mandatory a good use of the available resources. The parallel processing of neighborhood strategies is implemented at the fine grain level through GPU processing and coarse grain through multi-core processing and network processing, the combination of the two level parallelization in a heterogeneous environment for von Neumann architectures and dataflow Problemas de otimização são de grande importância para diversos setores da indústria, desde o planejamento de produção até escoamento e transporte de produtos. Diversos problemas de interesse se enquadram na classe NP-Difícil, sendo desconhecidos algoritmos para resolvê-los de forma exata em tempo polinomial. Assim, estratégias heurísticas com capacidade de escapar de ótimos locais de baixa qualidade (meta-heurísticas) são geralmente empregadas. A busca local é, em geral, a etapa mais custosa, em termos de tempo computacional, do processo de uma meta-heurística. Desta forma torna-se muito importante fazer bom uso dos recursos nela utilizados. Esta dissertação estuda o emprego de múltiplas estratégias de vizinhança utilizadas paralelamente para explorar um espaço de vizinhança maior e com melhor aproveitamento dos recursos computacionais. O processamento paralelo das estratégias de vizinhança é implementado em nível de grão fino, através de processamento em GPU, e grão grosso, por meio de processamento multi core e processamento em rede, sendo os dois níveis combinados num ambiente heterogêneo, para arquiteturas von Neumann e dataflow.

Nesta dissertação, tratamos de limites para o número envoltório e o número de Carathéodory na Convexidade P3. Aferimos resultados para grafos de diâmetro 2 com vértice de corte para ambos os problemas. Adentrando em casos mais complexos, conseguimos determinar um limite logarítmico, por meio de algoritmo pseudo-polimonial, para o número envoltório de grafos de diâmetro 2 biconexos. Explorando um pouco mais restritivamente, conseguimos determinar um limite constante para algumas subclasses de grafos de diâmetro 2, os grafos maximais sem triângulo. Não atendo somente aos resultados teóricos, realizamos também implementações e algoritmos para esses parâmetros. As implementações perfazem algoritmos heurísticos, paralelos e força bruta. Por fim, embora não diretamente relacionado, desenvolvemos uma algoritmo para geração de grafos de Moore, que pode ser um dos caminhos para encontrar o ultimo grafo de Moore, caso ele exista. Questão que remanesce desconhecido e procurada por 55 anos. In this work we present results and implementantions for hull and Carathéodory numbers in P3 convexity. We obtain results for graphs of diameter 2 having cut-vertex for both problems. Finally, entering more complex cases, we were able to determine a logarithmic limit, means of algorithm, for the hull number in case of graph diameter 2 and 2-connected. Exploring more restrictive cases, we determined a constant limit for some subclasses of graphs of diameter 2. We made also implementations and algorithms for these parameters. Implementations algorithms heuristic, parallel, and brute force. Finally, although not directly related, we developed an algorithm for Moore's graphs generation, which may be one of the ways to find Moore missinge graph, if it exists, a question that remains unknown for 55 years. And finally, we conclude with some conjectures interesting, for limits to the hull and Carathéodory numbers, in other classes of graphs, that were not explored in this work, but was identified by the implementations, and can be better explored in future works. Outro

Neste trabalho, investigamos o problema de se encontrar códigos identificadores de cardinalidade mínima em diversas classes de grafos, tais como árvores, produtos coronas, produtos Cartesianos e prismas complementares. Para árvores caterpillar, determinamos a cardinalidade mínima de um código identificador em caterpillars completo, grafos broom e broom duplo, e provamos um limite superior justo para caterpillars gerais. Para coronas, determinamos a cardinalidade mínima de um código identificador em $K_n \circ \overline{K}_m$. Para produtos Cartesianos, investigamos códigos identificadores em grafos $K_{1,n} \square P_m$, definimos um limite superior justo para o caso em que $n=3$ e um limite superior mais abrangente para o caso em que $n \geq 3$. Quando $n=3$, conjecturamos que o limite proposto é mínimo. Para prismas complementares de grafos, encontramos o tamanho de um código identificador mínimo em grafos bipartidos completos e grafos split completos. Para prismas complementares, obtivemos ainda outros resultados: demonstramos que um grafo prisma complementar $G\overline{G}$ é identificável se, e somente se, a ordem de $G$ é pelo menos dois; definimos o menor tamanho possível de um código identificador em um grafo $G\overline{G}$; determinamos um limite superior justo para o código identificador de um grafo conexo, mostrando também que seu conjunto de vértices é um conjunto identificador com o tamanho proposto e, finalmente, mostramos que o grafo bipartido completo é um exemplo de grafo que atinge a igualdade do limite superior apresentado. In this work, we investigate the problem of finding identifying codes of minimum size in a variety of graph classes, such as trees corona products, Cartesian products and complementary prisms. For caterpillar trees, we show the minimum size of an identifying code on complete caterpillars, brooms and double brooms. We also prove a sharp upper bound for the general case. For coronas $K_n \circ \overline{K}_m$, we prove what is the minimum size of an identifying code. We demonstrate a sharp upper bound for an identifying code of the Cartesian product of a star and a path $K_{1,n} \square P_m$ and, when $n=3$, we conjecture that the limit proposed is minimum. We also find the minimum cardinality of an identifying code in the complementary prism of complete bipartite graphs and complete split graphs, among with other results: we demonstrate that the complementary prism graph $G\overline{G}$ is identifiable if, and only if, $G$ has at least two vertices; we find what is the smallest size possible of an identifying code of complementary prisms; we prove a sharp upper bound for an identifying code of the complementary prism $G\overline{G}$ of a connected graph $G$, showing that the set $C = V(G)$ is an identifying code with the size proposed and, finally, we determine the size of a minimum identifying code of the complementary prism of a complete bipartite graph, showing that it is an example of a graph that attains our upper bound. Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES

Submitted by Aglair Aguiar (aglair@ct.ufrj.br) on 2019-10-18T17:32:15Z No. of bitstreams: 1 878071.pdf: 3990952 bytes, checksum: 2d210e5e6a8e0b2355b7d577cfce15f4 (MD5) Made available in DSpace on 2019-10-18T17:32:15Z (GMT). No. of bitstreams: 1 878071.pdf: 3990952 bytes, checksum: 2d210e5e6a8e0b2355b7d577cfce15f4 (MD5) Previous issue date: 2017-04 Esta tese aborda problemas associados a conversões em grafos e de edição pela remoção de um emparelhamento. Estudamos processos f-reversíveis, que são aqueles associados a um valor de limiar para cada vértice e cuja dinâmica depende da quantidade de vizinhos com estado contrário para cada vértice. Estabelecemos um limite superior justo para o tamanho do período e transiente, caracterizamos todas as árvores que alcançam o transiente máximo em processos 2-reversíveis e mostramos que determinar o tamanho de um conjunto conversor mínimo é NP-difícil. Mostramos que o modelo AND-OR define uma convexidade sobre grafos. Mostramos resultados de NP-completude e algoritmos eficientes para certos parâmetros de convexidade para esta nova, assim como algoritmos aproximativos. Introduzimos o conceito de processos de limiar generalizados, onde mostramos resultados de NP-completude e algoritmos eficientes para ambas as versões não relaxada e relaxada. Estudamos o problema de decidir se um dado grafo admite uma remoção de um emparelhamento de modo a remover todos os ciclos. Mostramos que este problema é NP-difícil mesmo para grafos subcúbicos, mas admite solução eficiente para várias classes de grafos. Estudamos o problema de decidir se um dado grafo admite uma remoção de um emparelhamento de modo a remover todos os ciclos ímpares. Mostramos que este problema é NP-difícil mesmo para grafos planares com grau limitado, mas admite solução eficiente para algumas classes de grafos. Mostramos também resultados parametrizados. This thesis addresses the problems associated with conversions on graphs and editing by removing a matching. We study the f-reversible processes, which are those associated with a threshold value for each vertex, and whose dynamics depends on the number of neighbors with different state for each vertex. We set a tight upper bound for the period and transient lengths, characterize all trees that reach the maximum transient length for 2-reversible processes, and we show that determining the size of a minimum conversion set is NP-hard. We show that the AND-OR model defines a convexity on graphs. We show results of NP-completeness and efficient algorithms for certain convexity parameters for this new one, as well as approximate algorithms. We introduce the concept of generalized threshold processes, where the results are NP-completeness and efficient algorithms for both non relaxed and relaxed versions. We study the problem of deciding whether a given graph admits a removal of a matching in order to destroy all cycles. We show that this problem is NP-hard even for subcubic graphs, but admits efficient solution for several graph classes. We study the problem of deciding whether a given graph admits a removal of a matching in order to destroy all odd cycles. We show that this problem is NP-hard even for planar graphs with bounded degree, but admits efficient solution for some graph classes. We also show parameterized results.

Submitted by Christianne Fontes de Andrade (cfontes@ct.ufrj.br) on 2019-05-23T15:42:49Z No. of bitstreams: 1 878290.pdf: 2254105 bytes, checksum: aa84953b057b1c76cfbc42fecf599b3a (MD5) Made available in DSpace on 2019-05-23T15:42:49Z (GMT). No. of bitstreams: 1 878290.pdf: 2254105 bytes, checksum: aa84953b057b1c76cfbc42fecf599b3a (MD5) Previous issue date: 2017-02 Uma árvore de conexão de um grafo G para um subconjunto não vazio W ⊆ V (G) é um subgrafo T de G tal que T é uma árvore, W ⊆ V (T) e todas as folhas de T pertencem a W. Os vértices em W são chamados de terminais, os vértices em V (T) \ W com grau exatamente 2 em T são chamados de elos e os vértices em V (T) \ W com grau ao menos 3 em T são chamados de roteadores. Em 2012, Dourado et al. propuseram o Problema de conexão de terminais (TCP), o qual consiste na seguinte questão: “dado um grafo conexo G, um conjunto de terminais W e dois inteiros não negativos ` e r; G admite uma árvore de conexão para W que contenha no máximo ` elos e no máximo r roteadores? ”. O TCP foi provado ser NP-completo mesmo quando ou ` ou r é limitado por uma constante; por outro lado, o problema foi provado ser solucionável em tempo polinomial se ` e r são ambos limitados por constantes. Posteriormente, em 2014, Dourado et al. propuseram a variante estrita do TCP na qual exige-se adicionalmente que todos os terminais sejam folhas de T, denotada por S-TCP. De igual modo ao TCP, o S-TCP foi provado ser NP-completo se ` é limitado por uma constante e ser solucionável em tempo polinomial se ` e r são ambos limitados por constantes; contudo, o caso em que apenas r é limitado por uma constante não havia sido considerado até então. Assim, estudamos o S-TCP restrito ao caso em que r é limitado por uma constante. Mais especificamente, propomos um algoritmo de tempo polinomial para o S-TCP quando r ∈ {0, 1} e provamos resultados parciais para quando r ≥ 2, exibindo relações com problemas de fluxo em redes e caminhos disjuntos. Ademais, determinamos a complexidade de algumas variantes do S-TCP. Por fim, estudamos o S-TCP e o TCP quando o grau máximo do grafo G é limitado. A connection tree of a graph G for a non-empty subset W ⊆ V (G) is a tree subgraph of G such that W ⊆ V (T) and every leaf of T belongs to W. The vertices in W are called terminals, the vertices in V (T) \ W with degree 2 in T are called linkers and the vertices in V (T) \ W with degree at least 3 in T are called routers. In 2012, Dourado et al. proposed the Terminal connection problem (TCP), which consists in the following question: “given a connected graph G, a terminal set W and two non-negative integers ` and r; does G admit a connection tree for W such that it has at most ` linkers and at most r routers? ”. The TCP was proved to be NP-complete even when either ` or r is bounded by a constant; conversely, the problem was proved to be polynomial-time solvable if ` and r are both bounded by constants. Later, in 2014, Dourado et al. proposed the strict variant of the TCP which further requires that every terminal must be a leaf of T, and it is denoted by S-TCP. As the TCP, the S-TCP was proved to be NP-complete if ` is bounded by a constant and be polynomial-time solvable if ` and r are both bounded by constants; however, the case in which just r is bounded by a constant was not considered. Thus, we study in this dissertation the S-TCP restricted to the case in which r is bounded by a constant. More specifically, we provide a polynomial-time algorithm for the S-TCP when r ∈ {0, 1} and we prove partial results for the case r ≥ 2, exposing relations with network flows and disjoint paths. Moreover, we determine the complexity of some variants of the S-TCP. Lastly, we study the S-TCP and the TCP when the maximum degree of the graph G is bounded.

Orientadores: Lehilton Lelis Chaves Pedrosa, Flávio Keidi Miyazawa, Rafael Crivellari Saliba Schouery Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O problema do Localização de Instalações (FLP, do inglês \emph{Facility Location Problem}) é um problema de Otimização Combinatória no qual instalações precisam ser construídas para satisfazer a demanda de um conjunto de clientes. Esse problema possui aplicação em muitas áreas, como serviços de saúde, transporte, logística e produção. Nesta dissertação, discutiremos algoritmos de aproximação para algumas generalizações do FLP: o $k$-LFLP (FLP em $k$ níveis), no qual instalações são organizadas hierarquicamente e clientes são atendidos por cadeias de instalações de todos os níveis hierárquicos; o FLP Dinâmico e Estocástico (respectivamente DFLP e SFLP), onde custos de abertura e a demanda de clientes muda através do tempo; e variações do FLP Estocástico em $k$-Níveis ($k$-LSFLP) que combinam elementos de ambos os problemas anteriores. Inicialmente, revisamos resultados para o $k$-LFLP, DFLP e SFLP que utilizamos posteriormente para obter algoritmos de aproximação para o $k$-LSFLP e sua variação de ''Restrição de Estágio'' ($k$-LSSCFLP). Para o $k$-LSFLP, obtivemos uma $(2k -1 +o(1))$-aproximação cujo fator de aproximação é $3.495$, $5.157$ e $7.034$ para, respectivamente, $k=2,3$ e $4$. E, para o $k$-LSSCFLP, obtivemos uma $(4-o(1))$-aproximação que possui fator de $2.56$, $2.68$ e $2.95$ para $k=2,3$ e $4$ respectivamente Abstract: The Facility Location Problem (FLP) is a Combinatorial Optimization problem in which some facilities must be built to satisfy demands of a set of clients. It has applications in many areas such as health services, transportation, logistics and production. In this thesis, we will discuss approximation algorithms for some generalizations of the FLP: the $k$-Level FLP ($k$-LFLP), where facilities are organized hierarchically and clients are satisfied by chains of facilities spanning all levels; the Dynamic and Stochastic FLP (DFLP and SFLP, respectively), where opening costs and client demands change over time; and variations of the $k$-Level Stochastic FLP ($k$-LSFLP) that combines elements of both previous problems. We first review results for the $k$-LFLP, DFLP and SFLP that we later utilize to provide approximation algorithms for the $k$-LSFLP and the ''Stage Constrained'' $k$-LSFLP ($k$-LSSCFLP). For the $k$-LSFLP, we obtain a $(2k - 1 + o(1))$-approximation whose approximation factor is $3.495$, $5.157$ and $7.034$ for, respectively, $k=2,3$ and $4$. And, for the $k$-LSSCFLP, we obtain a $(4 - o(1))$-approximation that has approximation factor of $2.56$, $2.68$ and $2.95$ for $k=2,3$ and $4$ respectively Mestrado Ciência da Computação Mestre em Ciência da Computação CAPES 1364110, 1406909 CNPQ 154329/2015-0