Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Deciding Morality of Graphs is NP-complete
Tom Verma, Judea Pearl
Abstract:
In order to find a causal explanation for data presented in the form of covariance and concentration matrices it is necessary to decide if the graph formed by such associations is a projection of a directed acyclic graph (dag). We show that the general problem of deciding whether such a dag exists is NP-complete.
Keywords:
Pages: 391-399
PS Link:
PDF Link: /papers/93/p391-verma.pdf
BibTex:
@INPROCEEDINGS{Verma93,
AUTHOR = "Tom Verma and Judea Pearl",
TITLE = "Deciding Morality of Graphs is NP-complete",
BOOKTITLE = "Proceedings of the Ninth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-93)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1993",
PAGES = "391--399"
}


hosted by DSL   •   site info   •   help