Finding Minimal d-separators in Linear Time and Applications
Finding Minimal d-separators in Linear Time and Applications
复制标题
寻找线性时间中的最小 d 分隔符及其应用
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Liskiewicz
中科院分区：
文献类型：
--
作者：
Benito van der Zander;M. Liskiewicz
对图形因果模型的研究基本上是对分离和条件独立性的研究。我们提供了两个图基元的线性时间算法：测试给定集是否为最小d -分隔符，以及在有向无环图（dag）、完全部分有向无环图（cpdag）和限制链图（RCGs）中找到最小d -分隔符，以及在祖先图（AGs）中找到最小m -分隔符。这些算法改进了先前已知的基于道德的最小分隔符算法的运行时间，因此需要二次时间来构建和处理道德图。（最小）分离集有重要的应用，如寻找（最小）协变量调整集或条件工具变量。
The study of graphical causal models is fundamentally the study of separations and conditional independences. We provide linear-time algorithms for two graphical primitives: to test, if a given set is a minimal d -separator, and to find a minimal d -separator in directed acyclic graphs (DAGs), completed partially directed acyclic graphs (CPDAGs) and restricted chain graphs (RCGs) as well as minimal m - separators in ancestral graphs (AGs). These algorithms improve the runtime of the best previously known algorithms for minimal separators that are based on moralization and thus require quadratic time to construct and handle the moral graph. (Minimal) separating sets have important applications like finding (minimal) covariate adjustment sets or conditional instrumental variables.
影响因子：
7.7
作者：
Textor, Johannes;van der Zander, Benito;Ellison, George T. H.
通讯作者：
Ellison, George T. H.
马尔可夫等效 DAG 中的分隔符和调整集
DOI：
10.1609/aaai.v30i1.10424
发表时间：
2016
期刊：
影响因子：
--
作者：
Benito van der Zander;Maciej Liśkiewicz
通讯作者：
Maciej Liśkiewicz