Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/14043
Tipo: Tese
Título: Estudo da complexidade de grafos bem cobertos-(r,l) : reconhecimento, problemas sanduíche e probe
Título(s) alternativo(s): A complexity approach of the (r,l)-well-covered graphs: recognition, sandwich problems and probe
Autor(es)/Inventor(es): Alves, Sancrey Rodrigues
Orientador: Klein, Sulamita
Coorientador: Faria, Luerbio
Coorientador: Couto, Fernanda Vieira Dias
Resumo: [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
Resumo: [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.
Palavras-chave: Teoria dos grafos
Partições em grafos
Grafos bem cobertos
Problemas sanduíche
Problemas probe
Assunto CNPq: CNPQ::ENGENHARIAS
Programa: Programa de Pós-Graduação em Engenharia de Sistemas e Computação
Unidade produtora: Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Editora: Universidade Federal do Rio de Janeiro
Data de publicação: Dez-2019
País de publicação: Brasil
Idioma da publicação: por
Tipo de acesso: Acesso Aberto
Aparece nas coleções:Engenharia de Sistemas e Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
SancreyRodriguesAlves.pdf3.47 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.