Finding Minimal Separators in LWF Chain Graphs

Mohammad Ali Javidian, Marco Valtorta
Proceedings of the Ninth International Conference on Probabilistic Graphical Models, PMLR 72:193-200, 2018.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v72-javidian18a, title = {Finding Minimal Separators in LWF Chain Graphs}, author = {Javidian, Mohammad Ali and Valtorta, Marco}, booktitle = {Proceedings of the Ninth International Conference on Probabilistic Graphical Models}, pages = {193--200}, year = {2018}, editor = {Kratochvíl, Václav and Studený, Milan}, volume = {72}, series = {Proceedings of Machine Learning Research}, month = {11--14 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v72/javidian18a/javidian18a.pdf}, url = {https://proceedings.mlr.press/v72/javidian18a.html}, 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.} }
Endnote
%0 Conference Paper %T Finding Minimal Separators in LWF Chain Graphs %A Mohammad Ali Javidian %A Marco Valtorta %B Proceedings of the Ninth International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2018 %E Václav Kratochvíl %E Milan Studený %F pmlr-v72-javidian18a %I PMLR %P 193--200 %U https://proceedings.mlr.press/v72/javidian18a.html %V 72 %X 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.
APA
Javidian, M.A. & Valtorta, M.. (2018). Finding Minimal Separators in LWF Chain Graphs. Proceedings of the Ninth International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 72:193-200 Available from https://proceedings.mlr.press/v72/javidian18a.html.

Related Material