Autores

6810
2340,414,413,3044
6811
2340,414,413,3044
6812
2340,414,413,3044
6813
2340,414,413,3044

Informações:

Publicações do PESC

Título
Estudo da Complexidade de Grafos Bem Cobertos-(r,l): Reconhecimento, Problemas Sanduíche e Probe
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
12/12/2019
Resumo

Uma partição-(r,l) de um grafo G é uma partição do seu conjunto de vértices em r conjuntos independentes e l 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 l 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 proporcional de um conjunto independente maximal do grafo de entrada, diversidade de vizinhança, e o número l de cliques em uma partição-(r,l).

Abstract

A (r,l)-partition of a graph G is a partition of its vertex set into r independent sets and l 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 l cliques are provided as input, and the question is whether G is well-covered.

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 PARTITION PROBE FOR (r,l)-WELL-COVERED 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 proportional of a maximal independent set of the input graph, neighborhood diversity, and the number l of cliques in an (r,l)-partition.

Arquivo
Topo