Particionamento de Grafos Cordais em Conjuntos Independentes e Cliques

Authors

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

DOI:

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

Abstract

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.

References

[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

Published

2002-06-01

How to Cite

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

Issue

Vol. 3 No. 1 (2002)

Section

Original Article

License

Copyright

Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.

Intellectual Property and Terms of Use

The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.

The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.