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 = {Václav Kratochvíl and Milan Studený}, volume = {72}, series = {Proceedings of Machine Learning Research}, address = {Prague, Czech Republic}, month = {11--14 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v72/javidian18a/javidian18a.pdf}, url = {http://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 %J Proceedings of Machine Learning Research %P 193--200 %U http://proceedings.mlr.press %V 72 %W PMLR %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 PMLR 72:193-200

Related Material