Estudo da complexidade de grafos bem cobertos-(r,l) : reconhecimento, problemas sanduíche e probe

• Ano de defesa: 2019
• Autor(a) principal: Alves, Sancrey Rodrigues
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Rio de Janeiro; Brasil; Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia; Programa de Pós-Graduação em Engenharia de Sistemas e Computação; UFRJ
• Palavras-chave em Português: Teoria dos grafos; Partições em grafos; Grafos bem cobertos; Problemas sanduíche; Problemas probe; CNPQ::ENGENHARIAS
• Link de acesso: http://hdl.handle.net/11422/14043

[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.