Junction trees of general graphs

Xiaofei Wang; Jianhua Guo

doi:10.1007/s11464-008-0023-z

Front. Math. China ›› 2008, Vol. 3 ›› Issue (3) : 399 -413. DOI: 10.1007/s11464-008-0023-z

Research Article

Junction trees of general graphs

Xiaofei Wang ¹
, Jianhua Guo ¹^,^b

Author information +

History +

PDF (182KB)

Abstract

In this paper, we study the maximal prime subgraphs and their corresponding structure for any undirected graph. We introduce the notion of junction trees and investigate their structural characteristics, including junction properties, induced-subtree properties, running-intersection properties and maximum-weight spanning tree properties. Furthermore, the characters of leaves and edges on junction trees are discussed.

Keywords

Junction property / junction tree / P-decomposition / running-intersection property

Cite this article

Download citation ▾

Xiaofei Wang, Jianhua Guo. Junction trees of general graphs. Front. Math. China, 2008, 3(3): 399-413 DOI:10.1007/s11464-008-0023-z

登录浏览全文

4963

注册一个新账户忘记密码

References

Publishing order | Descend order by publishing year | Descend order by cited within

[1]	Berry A., Bordat J. P. Separability generalizes Dirac’s theorem. Discrete Applied Mathematics, 1998, 84: 43-53.

[2]	Blair J. R. S., Peyton B. W. George J. A., Liu J. W. H. An introduction to chordal graphs and clique trees. Sparse Matrix Computations: Graph Theory Issues and Algorithms, IMA Volumes in Mathematics and Its Applications, 1993, Berlin: Springer-Verlag, 1-30.

[3]	Buneman P. A characterization of rigid circuit graphs. Discrete Math, 1974, 9: 205-212.

[4]	Darroch J. N., Lauritzen S. L., Speed T. P. Markov fields and log-linear interaction models for contingency tables. Ann Statist, 1980, 8: 522-539.

[5]	Diestel R. Graph Decomposition-A Study in Infinite Graph Theory, 1990, Oxford: Clarendon Press.

[6]	Dirac G. A. On rigid circuit graphs. Abh Math Sem Univ Hamburg, 1961, 25: 71-76.

[7]	Gavril F. The intersection graphs of subtrees in trees are exactly the chordal graphs. J Combin Theory, Ser B, 1974, 16: 47-56.

[8]	Leimer H. G. Optimal decomposition by clique separators. Discrete Math, 1993, 113: 99-123.

[9]	Lekkerkerker C. G., Boland J. C. Representation of a finite graph by a set of intervals on the real line. Fund Math Polska Akad Nauk, 1962, 51: 45-64.

[10]	Tarjan R. E. Decomposition by clique separators. Discrete Math, 1985, 55: 221-232.

[11]	Walter J. Representations of rigid cycle graphs. Dissertation for the Doctoral Degree. Detroit: Wayne State University, 1972

[12]	Xu P. F., Guo J. H. Optimal triangulation of Bayesian networks by decomposition. Technical Report KLAS#07-003, 2007, Changchun: Northeast Normal University.