Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
R. Ganian, T. Hamm, T. Talvitie:
"An Efficient Algorithm for Counting Markov Equivalent DAGs";
Vortrag: 34th AAAI Conference on Artificial Intelligence (AAAI-20),
New York, New York, USA;
07.02.2020
- 12.02.2020; in: "The Thirty-Fourth AAAI Conference on Artificial Intelligence",
AAAI Press,
34
(2020),
ISSN: 2159-5399;
S. 10136
- 10143.
Kurzfassung englisch:
We consider the problem of counting the number of DAGs
which are Markov-equivalent, i.e., which encode the same
conditional independencies between random variables. The
problem has been studied, among others, in the context of
causal discovery, and it is known that it reduces to counting
the number of so-called moral acyclic orientations of certain
undirected graphs, notably chordal graphs.
Our main empirical contribution is a new algorithm which
outperforms previously known exact algorithms for the considered
problem by a significant margin. On the theoretical
side, we show that our algorithm is guaranteed to run in polynomial
time on a broad class of chordal graphs, including interval
graphs.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1609/aaai.v34i06.6573
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_293759.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.