← Back to papers
2018 PGM PGM 2018

Finding Minimal Separators in LWF Chain Graphs

Abstract

We address the problem of finding a minimal separator in a LWF chain graph, namely, finding a set $Z$ of nodes that separates a given non-adjacent pair of nodes such that no proper subset of $Z$ separates that pair. We analyze several versions of this problem and offer polynomial time algorithms for each. These include finding a minimal separator from a restricted set of nodes, finding a minimal separator for two given disjoint sets, and testing whether a given separator is minimal.

🌉 Interdisciplinary Bridge — Computer Science and Machine Learning and Mathematics & Optimization
🧭 Keyword Pioneer — minimal separator
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Reinforcement Learning
🐣 Hot Topic Early Bird — graph theory

Authors

Mohammad Ali Javidian , Marco Valtorta

Topics

Mathematics & Optimization > Mathematics > Graph Theory Computer Science > Foundations > Algorithms Machine Learning > Bayesian & Probabilistic > Probabilistic Modeling Machine Learning > Core Methods > Graphical Models

Keywords

graph theory probabilistic graphical model polynomial time algorithm graph algorithm markov network minimal separator lwf chain graph graph node separation
Download PDF

Related papers

Discriminative Training of Sum-Product Networks by Extended Baum-Welch 2018
Learning Bayesian network classifiers with completed partially directed acyclic graphs 2018
Causal Structure Learning via Temporal Markov Networks 2018
A Bayesian Approach for Inferring Local Causal Structure in Gene Regulatory Networks 2018
Markov Random Field MAP as Set Partitioning 2018