Name
Title | ||
|---|---|---|
An alternative proof that exact inference problem in bayesian belief networks is NP-hard |
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11569596_96 | ISCIS |
Keywords | Field | DocType |
polynomially solvable class,new transformation,alternative polynomial time transformation,approximation version,well-known vertex cover problem,various application area,belief network,bayesian belief network,exact inference problem,new insight,alternative proof,polynomial time,vertex cover | Probabilistic inference,Discrete mathematics,Inference,Computer science,Theoretical computer science,Bayesian network,Artificial intelligence,Vertex cover,Bayesian statistics,Time complexity | Conference |
Volume | ISSN | ISBN |
3733 | 0302-9743 | 3-540-29414-7 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mustafa Tacettin | 1 | 0 | 0.34 |
| Tonguç Ünlüyurt | 2 | 102 | 8.94 |