Autores

6327
414,413,2870
6328
414,413,2870
6329
414,413,2870

Informações:

Publicações do PESC

Título
Problemas de Cortes de Arestas Máximos e Mínimos em Grafos
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
24/1/2017
Resumo

Iniciamos este trabalho mostrando que o problema do Corte Máximo Simples (SIMPLE MAXCUT) em grafos fortemente cordais é NP-completo, o que resolve um problema em aberto da Coluna Johnson [47] . Determinamos em seguida um algoritmo 2/3-aproximativo para este problema em grafos split e resolvemos o problema para a subclasse dos grafos (k,n)-split cheios, determinando exatamente um corte máximo simples. Partimos então para o estudo da complexidade parametrizada do problema: apoiados no problema da determinação do subgrafo balanceado de tamanho máximo em um grafo sinalizado que generaliza o problema do Corte Máximo Simples mostramos que este ultimo problema é tratável por parâmetro fixo em grafos split e grafos (r,l) exibindo um núcleo quadrático em ambos os casos. Obtivemos também núcleo linear para a subclasse dos grafos d*-split. Finalmente consideramos os problemas de cortes máximo e mínimo de arestas em um grafo aresta-colorido, mostramos que ambos são problemas NP-completos mesmo em grafos completos e são tratáveis por parâmetro fixo.

Abstract

We start this work showing that SIMPLE MAXCUT restricted to strongly chordal graphs is NP-complete, posed as open on Johnson's Column [47] . Next we find a 2/3-approximative algorithm to solve this problem for split graphs and we find an exact algorithm for full (k,n)-split graphs. As we already know that this problem is NP-complete for generic graphs, we study its parameterized complexity using the problem: given a signed graph G we want to find a balanced signed subgraph of G with maximum size. This problem is a generalization of SIMPLE MAXCUT. We prove that SIMPLE MAXCUT is fixed parameter tractable on split graphs and (r,l) graphs exhibiting a quadratic kernel in both cases. We also find a linear kernel for d*-split graphs. At last we consider the problems of MAXCUT and MINCUT on edge colored graphs, we show that both problems are NP-complete even on complete graphs and these problems are FPT.

Arquivo
Topo