Particionamento de Grafos Cordais em Conjuntos Independentes e Cliques
2002; Sociedade Brasileira de Matemática Aplicada e Computacional; Volume: 3; Issue: 1 Linguagem: Português
10.5540/tema.2002.03.01.0147
ISSN2179-8451
AutoresPavol Hell, Sulamita Klein, Loana Tito Nogueira, Fábio Protti,
Tópico(s)Graph theory and applications
ResumoNeste trabalho consideramos a seguinte generalizacao de grafos split: Um grafo G e um grafo-(k; l) se seu conjunto de vertices pode ser particionado em k conjuntos independentes e l cliques (uma clique e um subgrafo completo nao necessariamente maximal). Portanto, os grafos-(k; l) sao uma generalizacao dos grafos split, que correspondem aos grafos-(1; 1). Grafos split podem ser eficientemente reconhecidos [4]. Alem disso, os problemas classicos de otimizacao combinatoria sao tambem resolvidos eficientemente nessa classe. Na verdade, nosso resultado principal e uma caracterizacao de grafos cordais-(k; l). Tambem apresentamos um algoritmo para reconhecer grafos cordais-(k; l) cuja complexidade e O(n(m + n)). Quando k = l = 1, nosso algoritmo possui complexidade O(m + n). Em particular, obtivemos um algoritmo mais simples e eficiente apra reconhecer grafos split, do qual torna-se facil derivar a conhecida caracterizacao de grafos split por subgrafos proibidos.
Referência(s)