title   
  

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

Abstract

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.

Item Type:Article
Subjects:Q Science > QA Mathematics
ID Code:549
Deposited By:Tonguç Ünlüyurt
Deposited On:28 Nov 2005 02:00
Last Modified:13 May 2009 14:12

Repository Staff Only: item control page