Skip to main content
SpringerLink
Log in

Heuristic algorithms for the triangulation of graphs

  • Networks
  • Conference paper
  • First Online:
Advances in Intelligent Computing — IPMU '94 (IPMU 1994)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 945))

Abstract

Different uncertainty propagation algorithms in graphical structures can be viewed as a particular case of propagation in a joint tree, which can be obtained from different triangulations of the original graph. The complexity of the resulting propagation algorithms depends on the size of the resulting triangulated graph. The problem of obtaining an optimum graph triangulation is known to be NP-complete. Thus approximate algorithms which find a good triangulation in reasonable time are of particular interest. This work describes and compares several heuristic algorithms developed for this purpose.

This work was supported by the Commission of the European Communities under project DRUMS2, BRA 6156

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Arnborg S., D.G. Corneil, A. Proskurowski (1987) Complexity of finding embeddings in a k-tree. SIAM Jour. Alg. Discr. Meth. 8, 277–284.

    Google Scholar 

  2. Cano J.E., M. Delgado, S. Moral (1993) An axiomatic framework for the propagation of uncertainty in directed acyclic graphs. International Journal of Approximate reasoning 8 253–280.

    Google Scholar 

  3. Chin H.L., G.F. Cooper (1989) Bayesian network inference using simulation. In: Uncertainty in Artificial Intelligence, 3 (Kanal, Levitt, Lemmer, eds.) North-Holland, 129–147.

    Google Scholar 

  4. Cooper G.F. (1988) Probabilistic inference using belief networks is NP-hard. Technical Report KSL-87-27, Stanford University, Stanford, California.

    Google Scholar 

  5. Cooper G.F. The computational complexity of probabilistic inference using bayesian belief networks is NP-hard. Artificial Intelligence 42, 393–405.

    Google Scholar 

  6. D'Ambrosio B. (1991) Symbolic probabilistic inference in belief nets. Department of Computer Science, Oregon State University.

    Google Scholar 

  7. Geman S., D. Geman (1984) Stochastic relaxation, Gibbs distributions, and the bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence 6, 721–741.

    Google Scholar 

  8. Henrion M. (1986) Propagating uncertainty by logic sampling in Bayes' networks. Technical Report, Department of Engineering and Public Policy, Carnegie-Mellon University.

    Google Scholar 

  9. Kjærulff U. (1990) Triangulation of graphs-algorithms giving total state space. R 90-09, Department of Mathematics and Computer Science, Institute for Electronic Systems, Aalborg University.

    Google Scholar 

  10. Olmsted, S.M.(1983). On representing and solving decision problems. Ph.D. thesis, Department of Engineering-Economic Systems, Stanford University, Stanford, CA.

    Google Scholar 

  11. Kong, A. (1986). Multivariate belief functions and graphical models. Ph.D. dissertation, Department of Statistics, Harvard University, Cambridge, MA.

    Google Scholar 

  12. Kim J.H., J. Pearl (1983) A computational model for causal and diagnostic reasoning in inference engines, Proceedings 8th IJCAI, Karlsruhe, Germany.

    Google Scholar 

  13. Lauritzen S.L., D.J. Spiegelharter (1988) Local computation with probabilities on graphical structures and their application to expert systems. J. of the Royal Statistical Society, B 50, 157–224.

    Google Scholar 

  14. Jensen F. V. Junction trees and decomposable hypergraphs, Research report, Judex Datasystemer A/S, Aalborg, Denmark.

    Google Scholar 

  15. Pearl J. (1986) A constraint-propagation approach to probabilistic reasoning. In: Uncertainty in Artificial Intelligence (L.N. Kanal, J.F. Lemmer, eds.) North-Holland, 357–370.

    Google Scholar 

  16. Pearl J. (1986) Fusion, propagation and structuring in belief networks. Artificial Intelligence 29 241–288.

    Google Scholar 

  17. Pearl J. (1988) Probabilistic Reasoning in Intelligent Systems. Morgan & Kaufman, San Mateo.

    Google Scholar 

  18. Shachter R.D. (1986) Evaluating influence diagrams. Operations Research 34, 871–882.

    Google Scholar 

  19. Shachter R.D. (1988) Probabilistic inference and influence diagrams. Operations Research 36, 589–605.

    Google Scholar 

  20. Shachter R.D., S.K. Andersen, P. Szlovits (1991) The equivalence of exact methods for probabilistic inference on belief networks. Submitted to Artificial Intelligence.

    Google Scholar 

  21. Shafer G., P.P. Shenoy (1990) Probability Propagation. Annals of Mathematical and Artificial Intelligence 2, 327–351.

    Google Scholar 

  22. Shenoy P.P., G. Shafer (1990) Axioms for probability and belief-functions propagation. In: Uncertainty in Artificial Intelligence, 4 (R.D. Shachter, T.S. Levitt, L.N. Kanal, J.F. Lemmer, eds.) North-Holland, Amsterdam, 169–198.

    Google Scholar 

  23. Tarjan R.E., M. Yannakakis (1984) Simple linear-time algorithm to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal of Computing 13 566–579.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Ciencias de la Computación e I.A., Universidad de Granada, 18071, Granada, Spain

    Andrés Cano & Serafín Moral

Authors
  1. Andrés Cano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Serafín Moral
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Bernadette Bouchon-Meunier Ronald R. Yager Lotfi A. Zadeh

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Cano, A., Moral, S. (1995). Heuristic algorithms for the triangulation of graphs. In: Bouchon-Meunier, B., Yager, R.R., Zadeh, L.A. (eds) Advances in Intelligent Computing — IPMU '94. IPMU 1994. Lecture Notes in Computer Science, vol 945. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0035941

Download citation

  • DOI: https://doi.org/10.1007/BFb0035941

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60116-6

  • Online ISBN: 978-3-540-49443-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation