Partições em Grafos com Poucos P4´s
Autores
|
5120 |
1908,413,2303
|
|
|
5121 |
1908,413,2303
|
|
|
5122 |
Loana Nogueira
(Co-orientador) |
1908,413,2303
|
Informações:
Publicações do PESC
Título
Partições em Grafos com Poucos P4´s
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
30/9/2011
Resumo
Este trabalho descreve um estudo de dois problemas de partição: o problema da partição (k,l) e o problema da partição-(C,F). O problema de partição-(k,l) consiste em particionar o conjunto de vértices em k conjuntos independentes e l cliques, que foi introduzido por Brandstädt, e generalizado por Feder, Hell, Klein e Motwani como o problema da M-partição. Brandstädt, provou que, dado um grafo G, é NP-completo decidir se G é um grafo (k,l) para k >= 3 ou l >= 3. Desde então, muitos trabalhos têm sido resolvidos para o problema da partição-(k,l) para algumas subclasses de grafos, tais como a classe dos grafos cordais. O problema da partição-(C,F) consiste em verificar se o conjunto de vértices de um grafo G pode ser particionado em dois subconjuntos C e F, tais que C é uma clique e F induz uma floresta. Embora o reconhecimento dos grafos-(C,F) seja polinomial, não se conhece na literatura nenhuma caracterização por subgrafos proibidos para grafos gerais. Consideramos os dois problemas citados acima para classes de grafos com poucos P4's. Mais especificamente, fornecemos uma caracterização por subgrafos proibidos mais explícita, que a já existente para os cografos-(k,l). Uma caracterização dos grafos P4-esparsos-(k,l) e um algoritmo de reconhecimento em tempo linear para a classe são apresentados. Nesta mesma linha, descrevemos um algoritmo de reconhecimento em tempo linear para a classe dos grafos P4-laden estendidos (k,l). Caracterizamos por subgrafos proibidos a classe dos grafos P4-esparsos-(C,F) e a classe dos grafos P4-tidy-(C,F), apresentando um algoritmo de reconhecimento em tempo linear para a classe, a qual contém a classe dos grafos P4-esparso-(C,F).
Abstract
This work describes a study on two partition problems: the (k,l)-partition problem and the (C,F) partition problem.
The (k,l)-partition problem consists the problem of partitioning the vertices of a graph into k independent sets and l cliques. This problem was introduced by Brandstädt, and generalized by Feder, Hell, Klein and Motwani as the M-partition problem. Brandstädt proved that given a graph G, it is NP-complete to decide if $G$ is a (k,l)-graph for k >= 3$ or l >= 3. Since then, many works have been done in order to solve the (k,l)-partition problem for many subclasses of graphs, such as chordal graphs. The (C,F)-partition problem consists of verifying if the set of vertices of a graph G can be partitioned into two subsets C and F, such that C is a clique and F induces a forest. Although the recognition of (C, F)-graphs is polynomial, there is not any known characterization of (C,F)-graphs by forbidden subgraphs for graphs in general. We consider both of the aformentioned problems for classes of graphs with a few P4's. More specifically, we provide a characterization by forbidden subgraphs more explicit than the existing one for (k,l)-cographs. A characterization of (k,l)-P4-sparse graphs and a linear-time recognition algorithm for this class are presented. Similarly, we describe a linear-time algorithm for the class of (k,l) extended P4-laden graphs and obtain the chocromatic number for this. Furthermore, we characterize the class of (C,F)-P4-sparse graphs and the class of (C,F)-P4-tidy graphs by forbidden subgraphs, featuring a linear-time algorithm to recognize the class of (C,F)-P4-tidy graphs, which contains the class of (C,F)-P4-sparse graphs.
The (k,l)-partition problem consists the problem of partitioning the vertices of a graph into k independent sets and l cliques. This problem was introduced by Brandstädt, and generalized by Feder, Hell, Klein and Motwani as the M-partition problem. Brandstädt proved that given a graph G, it is NP-complete to decide if $G$ is a (k,l)-graph for k >= 3$ or l >= 3. Since then, many works have been done in order to solve the (k,l)-partition problem for many subclasses of graphs, such as chordal graphs. The (C,F)-partition problem consists of verifying if the set of vertices of a graph G can be partitioned into two subsets C and F, such that C is a clique and F induces a forest. Although the recognition of (C, F)-graphs is polynomial, there is not any known characterization of (C,F)-graphs by forbidden subgraphs for graphs in general. We consider both of the aformentioned problems for classes of graphs with a few P4's. More specifically, we provide a characterization by forbidden subgraphs more explicit than the existing one for (k,l)-cographs. A characterization of (k,l)-P4-sparse graphs and a linear-time recognition algorithm for this class are presented. Similarly, we describe a linear-time algorithm for the class of (k,l) extended P4-laden graphs and obtain the chocromatic number for this. Furthermore, we characterize the class of (C,F)-P4-sparse graphs and the class of (C,F)-P4-tidy graphs by forbidden subgraphs, featuring a linear-time algorithm to recognize the class of (C,F)-P4-tidy graphs, which contains the class of (C,F)-P4-sparse graphs.
Arquivo