Autores

4274
413,1908
4275
413,1908

Informações:

Publicações do PESC

Título
Cografos-(K,L): Caracterização e Reconhecimento
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
31/3/2006
Resumo

Neste trabalho, consideramos o problema de particionar um grafo em k conjuntos independentes e 1 cliques, conhecido como o problema da (k, 1)- partição ou o problema dos grafos-(k, I), o qual foi introduzido por Brandstadt, e generalizado por Feder, Hell, Klein e Motwani como o problema da Mpartição. Brandstadt provou que, dado um grafo G, é NP-completo decidir se G é um grafo-(k, I) para k > 3 ou I > 3. Em particular, consideramos uma subclasse de grafos perfeitos: os cografos, que consistem de grafos sem P4 (caminho induzido com 4 vértices), e apresentamos uma caracterização dos cografos-(k, I) em termos de subgrafos proibidos, i. e., obstruções, além de um algoritmo linear para reconhecer tal classe. O algoritmo linear baseia-se no fato de que cliques máximas e conjuntos independentes máximos podem ser encontrados em tempo linear quando restritos a cografos..

Abstract

In this work we consider the problem of partitioning a graph into k independent sets and 1 diques, known as the (k, 1)-partition problem, which was introduced by Brandstadt, and generalized by Feder, Hell, Klein and Motwani as the M-partition problem. Brandstadt proved that, given a graph G, it is NP-complete to decide if G is a (k, 1)-graph for k > 3 or 1 > 3. In particular, we consider a subclass of perfect graphs: the cographs, which consist of graphs without Pq (induced path with 4 vertices), and we present a characterization of the (k, 1)-cographs in terms of forbidden subgraphs, i. e., obstructions. Moreover, we give a linear time algorithm to recognize such class, which is bmed on the fact that maximum cliques and maximum independent sets can be found in linear time for cographs.

Arquivo
Topo