Skip to main content
SpringerLink
Log in

Two methods for the generation of chordal graphs

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In this paper two methods for automatic generation of connected chordal graphs are proposed: the first one is based on new results concerning the dynamic maintenance of chordality under edge insertions; the second is based on expansion/merging of maximal cliques. Theoretical and experimental results are presented. In both methods, chordality is preserved along the whole generation process.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Alberts, D., Cattaneo, G., & Italiano, G. F. (1997). An empirical study of dynamic graph algorithms. ACM Journal of Experimental Algorithms, 6, 1–39.

    Article  Google Scholar 

  • Araujo, L. H. (2004). Algoritmos dinâmicos para manutenção de grafos cordais e periplanares. Ph.D. Thesis, Coppe-Produção, Universidade Federal do Rio de Janeiro, RJ, Brasil.

  • Blair, J. R. S., & Peyton, B. (1993). An introduction to chordal graphs and clique trees. In J. A. George, J. R. Gilbert & J. W. Liu (Eds.), IMA volumes in mathematics and its applications : Vol. 56. Graph theory and sparse matrix computation (pp. 1–29). Berlin: Springer.

    Google Scholar 

  • Berry, A., Heggernes, P., & Villanger, Y. (2003). A vertex incremental approach for dynamically maintaining chordal graphs. In Proceedings of the 14th international symposium on algorithms and computation (ISAAC 2003), Springer LNCS 2906, pp. 47–57.

  • Chandran, L. S., Ibarra, L., Ruskey, F., & Sawada, J. (2003). Generating and characterizing the perfect elimination orderings of a chordal graph. Theoretical Computer Science, 307, 303–317.

    Article  Google Scholar 

  • Deo, N., & Micikevicius, P. (2002). A new encoding for labeled trees employing a stack and a queue. Bulletin of the Institute of Combinatorics and Its Applications, 34, 77–85.

    Google Scholar 

  • Eppstein, D., Galil, Z., & Italiano, G. F. (1997). Sparsification—a technique for speeding up dynamic graph algorithms. Journal of the ACM, 44, 669–696.

    Article  Google Scholar 

  • Gavril, F. (1972). Algorithms for minimum coloring, minimum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM Journal on Computing, 1, 180–187.

    Article  Google Scholar 

  • Golumbic, M. C. (1980). Algorithmic graph theory and perfect graphs. New York: Academic.

    Google Scholar 

  • Ibarra, L. (2000). Fully dynamic algorithms for chordal graphs and split graphs. Technical Report DCS-262-IR, University of Victoria, http://facweb.cs.depaul.edu/ibarra/research.htm.

  • Kumar, P. S., & Madhavan, C. E. V. (2002). Clique tree generalization and new subclasses of chordal graphs. Discrete Applied Mathematics, 117, 109–131.

    Article  Google Scholar 

  • Markenzon, L., Vernet, O., & Araujo, L. H. (2004). Two methods for the generation of chordal graphs. Technical Report NCE-13/04, Universidade Federal do Rio de Janeiro.

  • Rose, D. J., Tarjan, R. E., & Lueker, G. (1976). Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5, 266–283.

    Article  Google Scholar 

  • Tarjan, R. E. (1983). Data structures and network algorithms. Philadelphia: SIAM.

    Google Scholar 

  • Tinhofer, G. (1990). Generating graphs uniformly at random. Computing Supplement, 7, 235–255.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Núcleo de Computação Eletrônica, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil

    Lilian Markenzon & Oswaldo Vernet

  2. Instituto Militar de Engenharia, Rio de Janeiro, Brazil

    Luiz Henrique Araujo

Authors
  1. Lilian Markenzon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Oswaldo Vernet
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Luiz Henrique Araujo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lilian Markenzon.

Additional information

L. Markenzon’s research is partially supported by grant 301068/2003-8, CNPq, Brazil.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Markenzon, L., Vernet, O. & Araujo, L.H. Two methods for the generation of chordal graphs. Ann Oper Res 157, 47–60 (2008). https://doi.org/10.1007/s10479-007-0190-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-007-0190-4

Keywords

Search

Navigation