Particionamento de Grafos Cordais em Conjuntos Independentes e Cliques

Autores

  • P. HELL
  • S. KLEIN
  • L. T. NOGUEIRA
  • F. PROTTI

DOI:

https://doi.org/10.5540/tema.2002.03.01.0147

Resumo

Neste trabalho consideramos a seguinte generalização de grafos split: Um grafo G é um grafo-(k; l) se seu conjunto de vértices pode ser particionado em k conjuntos independentes e l cliques (uma clique é um subgrafo completo não necessariamente maximal). Portanto, os grafos-(k; l) são uma generalização dos grafos split, que correspondem aos grafos-(1; 1). Grafos split podem ser eficientemente reconhecidos [4]. Além disso, os problemas clássicos de otimização combinatória são também resolvidos eficientemente nessa classe. Na verdade, nosso resultado principal é uma caracterização de grafos cordais-(k; l). Também apresentamos um algoritmo para reconhecer grafos cordais-(k; l) cuja complexidade é 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 fácil derivar a conhecida caracterização de grafos split por subgrafos proibidos.

Referências

[1] A. Brandst¨adt, Partitions of graphs into one or two independent sets and cliques, Discrete Mathematics, 152 (1996), 47-54.

A. Brandst¨adt, The complexity of some problems related to graph 3- colorability, Discrete Applied Mathematics, 89 (1998), 59-73.

T. Feder, P. Hell, S. Klein, and R. Motwani, Complexity of graph partition problems, em “The 31st Annual ACM Symposium on Theory of Computing - STOC’99” ( F. W. Thatcher and R. E. Miller, eds.), pp. 464-472, Plenum Press, New York, 1999.

S. Foldes and P. Hammer, Split Graphs, em “ 8th Southeastern Conf. on Combinatorics, Graph Theory and Computing” (F. Hoffman et al., eds.), pp. 311-315, Louisiana State Univ., Baton Rouge, Louisiana.

L. T. Nogueira, “ Grafos Split e Grafos Split Generalizados”, Tese de Mestrado, COPPE-Sistemas, Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ, Brazil, 1999.

M. R. Garey, D. S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems, Theoretical Computer Science, 1 (1976), 237-267.

M. C. Golumbic, “ Algorithmic Graph Theory and Perfect Graphs”, Academic Press, New York, 1980.

Downloads

Publicado

2002-06-01

Como Citar

HELL, P., KLEIN, S., NOGUEIRA, L. T., & PROTTI, F. (2002). Particionamento de Grafos Cordais em Conjuntos Independentes e Cliques. Trends in Computational and Applied Mathematics, 3(1), 147–155. https://doi.org/10.5540/tema.2002.03.01.0147

Edição

v. 3 n. 1 (2002)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.