An efficient algorithm for finding the largest chain graph according to a given chain graph

作者：Liu BJ; Zheng ZG^*; Zhao H

来源：Science in China Series A-Mathematics, 2005, 48(11): 1517-1530.

DOI：10.1360/04ys0202

• graphical Markov model
• chain graph
• largest chain graph
• protected arrows
• efficient algorithm

Chain graph (CG) is a general model of graphical Markov models. Some different chain graphs may describe the same conditional independence structure, then we say that these CGs are Markov equivalent. In 1990 Frydenberg showed that every class of Markov equivalent CGs has a CG which is called the largest chain graph with the greatest number of lines. This paper presents an efficient algorithm for finding the largest chain graph of the corresponding Markov equivalent class of a given CG. The computational complexity of the algorithm is 0(n(3)). It is more efficient than the complexity 0(n!) of the present algorithms. Also a more intuitive graphical characterization of the largest chain graph is provided based on the algorithm in this paper.

• 出版日期2005-11
• 单位华中师范大学; 北京大学