An alternative proof that exact inference problem in Bayesian belief networks is NP-hard
Tacettin, Mustafa and Ünlüyurt, Tonguç (2005) An alternative proof that exact inference problem in Bayesian belief networks is NP-hard. Lecture notes in computer science, 3733 . pp. 947-955. ISSN 0302-9743 (Print) 1611-3349 (Online)
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/11569596
Exact inference problem in belief networks has been well studied in the literature and has various application areas. It is known that this problem and its approximation version are NP-hard. In this study, an alternative polynomial time transformation is provided from the well-known vertex cover problem. This new transformation may lead to new insights and polynomially solvable classes of the exact inference problem in Bayesian belief networks.
Repository Staff Only: item control page