论文标题
用于计数和采样马尔可夫等效dag的多项式时间算法
Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs
论文作者
论文摘要
来自马尔可夫等效类别的定向无环图（DAG）的计数和均匀采样是图形因果分析中的基本任务。在本文中，我们表明这些任务可以在多项式时间内执行，从而解决了该领域的长期开放问题。我们的算法是有效的，易于实现。实验结果表明，该算法的表现明显胜过最先进的方法。
Counting and uniform sampling of directed acyclic graphs (DAGs) from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper, we show that these tasks can be performed in polynomial time, solving a long-standing open problem in this area. Our algorithms are effective and easily implementable. Experimental results show that the algorithms significantly outperform state-of-the-art methods.
