Projects per year
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.
|Number of pages||11|
|Publication status||Published - 2019|
|Event||35th Conference on Uncertainty in Artificial Intelligence - Tel Aviv, Israel|
Duration: 22.07.2019 → 25.07.2019
Conference number: 151391
|Conference||35th Conference on Uncertainty in Artificial Intelligence|
|Abbreviated title||UAI 2019|
|Period||22.07.19 → 25.07.19|
FingerprintDive into the research topics of 'Finding minimal d-separators in linear time and applications'. Together they form a unique fingerprint.
- 1 Finished