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 

作者机构：School of Mathematical Sciences Peking University Beijing China Department of Statistics Central China Normal University Wuhan China 

出 版 物：《Science China Mathematics》 (中国科学：数学（英文版）)

年 卷 期：2005年第48卷第11期

页      面：1517-1530页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：supported by the National Natural Science Foundation of China(Grant Nos..39930160&19871003) 

主　　题：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 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.