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

查看全文 作　　者：LIU Baijun,ZHENG Zhongguo & ZHAO Hui School of Mathematical Sciences, Peking University, Beijing 100871, China;Department of Statistics, Central China Normal University, Wuhan 430079, China 出　　处：《Science China Mathematics》索引2005年第48卷第11期,共14页 基　　金：supported by the National Natural Science Foundation of China(Grant Nos..39930160&19871003). 摘　　要：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 O(n3). It is more efficient than the complexity O(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. 关 键 词：GRAPHICAL MARKOV model,chain graph,largest CHAIN graph,protected arrows,efficient algorithm