{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:14:52Z","timestamp":1762100092448,"version":"3.30.2"},"reference-count":31,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2003,12,1]],"date-time":"2003-12-01T00:00:00Z","timestamp":1070236800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3552,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[2003,12]]},"DOI":"10.1016\/s0004-3702(03)00110-3","type":"journal-article","created":{"date-parts":[[2003,7,16]],"date-time":"2003-07-16T13:31:26Z","timestamp":1058362286000},"page":"213-225","source":"Crossref","is-referenced-by-count":10,"title":["Complexity of probabilistic reasoning in\u00a0directed-path singly-connected Bayes networks"],"prefix":"10.1016","volume":"151","author":[{"given":"Solomon E","family":"Shimony","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carmel","family":"Domshlak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0004-3702(03)00110-3_BIB001","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0004-3702(98)00043-5","article-title":"Approximating MAPs for belief networks is NP-hard and other theorems","volume":"102","author":"Abdelbar","year":"1998","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(03)00110-3_BIB002","series-title":"Proceedings of Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA","first-page":"248","article-title":"Graph orientations with no sink and an approximation for a hard case of #SAT","author":"Bubley","year":"1997"},{"issue":"4","key":"10.1016\/S0004-3702(03)00110-3_BIB003","first-page":"50","article-title":"Bayesian networks without tears","volume":"12","author":"Charniak","year":"1991","journal-title":"AI Magazine"},{"issue":"2\u20133","key":"10.1016\/S0004-3702(03)00110-3_BIB004","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/0004-3702(90)90060-D","article-title":"The computational complexity of probabilistic inference using Bayesian belief networks","volume":"42","author":"Cooper","year":"1990","journal-title":"Artificial Intelligence"},{"year":"1990","series-title":"Introduction to Algorithms","author":"Cormen","key":"10.1016\/S0004-3702(03)00110-3_BIB005"},{"issue":"1","key":"10.1016\/S0004-3702(03)00110-3_BIB006","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0004-3702(93)90036-B","article-title":"Approximating probabilistic inference in Bayesian belief networks is NP-hard","volume":"60","author":"Dagum","year":"1993","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(03)00110-3_BIB007","series-title":"Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence, Montreal, QB","first-page":"99","article-title":"Conditioning methods for exact and approximate inference in causal networks","author":"Darwiche","year":"1995"},{"issue":"1\u20132","key":"10.1016\/S0004-3702(03)00110-3_BIB008","first-page":"5","article-title":"Recursive conditioning","volume":"125","author":"Darwiche","year":"2000","journal-title":"Artificial Intelligence (Special Issue on Resource Bounded Reasoning)"},{"key":"10.1016\/S0004-3702(03)00110-3_BIB009","series-title":"Proceedings of 15th International Conference on Uncertainty in Artificial Intelligence, Stockholm, Sweden","first-page":"134","article-title":"Learning polytrees","author":"Dasgupta","year":"1999"},{"issue":"1\u20132","key":"10.1016\/S0004-3702(03)00110-3_BIB010","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(95)00118-2","article-title":"Local conditioning in Bayesian networks","volume":"87","author":"Diez","year":"1996","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(03)00110-3_BIB011","series-title":"Proceedings of the Sixth International Conference on AI Planning and Scheduling, Toulouse, France","first-page":"34","article-title":"Structure and complexity in planning with unary operators","author":"Domshlak","year":"2002"},{"year":"1979","series-title":"Computers and Intractability, A Guide to the Theory of NP-completeness","author":"Garey","key":"10.1016\/S0004-3702(03)00110-3_BIB012"},{"key":"10.1016\/S0004-3702(03)00110-3_BIB013","series-title":"Proc. 5th Workshop on Uncertainty in AI, Windsor, ON","first-page":"182","article-title":"Bounded conditioning: Flexible inference for decisions under scarce resources","author":"Horvitz","year":"1989"},{"key":"10.1016\/S0004-3702(03)00110-3_BIB014","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1002\/net.3230200509","article-title":"An algebra of Bayesian belief universes for knowledge-based systems","volume":"20","author":"Jensen","year":"1990","journal-title":"Networks"},{"issue":"3\u20134","key":"10.1016\/S0004-3702(03)00110-3_BIB015","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0020-0190(99)00135-0","article-title":"An O(V2) algorithm for single connectedness","volume":"72","author":"Khuller","year":"1999","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0004-3702(03)00110-3_BIB016","series-title":"Proceedings IJCAI-83, Karlsruhe, Germany","first-page":"190","article-title":"A computation model for causal and diagnostic reasoning in inference systems","author":"Kim","year":"1983"},{"key":"10.1016\/S0004-3702(03)00110-3_BIB017","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","article-title":"Local computations with probabilities on graphical structures and their applications to expert systems","volume":"50","author":"Lauritzen","year":"1988","journal-title":"J. Royal Statist. Soc."},{"key":"10.1016\/S0004-3702(03)00110-3_BIB018","series-title":"Proceedings of 14th International Conference on Uncertainty in Artificial Intelligence, Madison, WI","first-page":"328","article-title":"A comparison of Lauritzen\u2013Spiegelhalter, Hugin, and Shenoy\u2013Shafer architectures for computing marginals of probability distributions","author":"Lepar","year":"1998"},{"year":"1990","series-title":"Probabilistic Reasoning in Expert Systems","author":"Neapolitan","key":"10.1016\/S0004-3702(03)00110-3_BIB019"},{"key":"10.1016\/S0004-3702(03)00110-3_BIB020","series-title":"Proceedings of Eighteenth Conference on Uncertainty in AI, Edmonton, AB","first-page":"388","article-title":"MAP complexity results and approximation methods","author":"Park","year":"2002"},{"year":"1988","series-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"Pearl","key":"10.1016\/S0004-3702(03)00110-3_BIB021"},{"key":"10.1016\/S0004-3702(03)00110-3_BIB022","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1109\/TSMC.1987.4309027","article-title":"A probabilistic causal model for diagnostic problem solving (parts 1 and 2)","volume":"SMC-17","author":"Peng","year":"1987","journal-title":"IEEE Trans. Systems Man Cybernet."},{"issue":"1","key":"10.1016\/S0004-3702(03)00110-3_BIB023","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0004-3702(93)90061-F","article-title":"Probabilistic Horn abduction and Bayesian networks","volume":"64","author":"Poole","year":"1993","journal-title":"Artificial Intelligence"},{"issue":"1\u20132","key":"10.1016\/S0004-3702(03)00110-3_BIB024","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0004-3702(96)00022-7","article-title":"Probabilistic conflicts in a search algorithm for estimating posterior probabilities in Bayesian networks","volume":"88","author":"Poole","year":"1996","journal-title":"Artificial Intelligence"},{"issue":"1\u20132","key":"10.1016\/S0004-3702(03)00110-3_BIB025","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(94)00092-1","article-title":"On the hardness of approximate reasoning","volume":"82","author":"Roth","year":"1996","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(03)00110-3_BIB026","series-title":"Uncertainty in AI, Proceedings of the Tenth Conference, Seattle, WA","first-page":"506","article-title":"Belief updating by enumerating high-probability independence-based assignments","author":"Santos","year":"1994"},{"issue":"6","key":"10.1016\/S0004-3702(03)00110-3_BIB027","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1287\/opre.34.6.871","article-title":"Evaluating influence diagrams","volume":"34","author":"Shachter","year":"1986","journal-title":"Oper. Res."},{"issue":"2","key":"10.1016\/S0004-3702(03)00110-3_BIB028","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/0004-3702(94)90072-8","article-title":"Finding MAPs for belief networks is NP-hard","volume":"68","author":"Shimony","year":"1994","journal-title":"Artificial Intelligence"},{"year":"1993","series-title":"Foundations of Constraint Satisfaction","author":"Tsang","key":"10.1016\/S0004-3702(03)00110-3_BIB029"},{"key":"10.1016\/S0004-3702(03)00110-3_BIB030","series-title":"Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, Providence, RI","first-page":"458","article-title":"NP is as easy as detecting unique solutions","author":"Valiant","year":"1985"},{"issue":"1","key":"10.1016\/S0004-3702(03)00110-3_BIB031","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1162\/089976600300015880","article-title":"Correctness of local probability propagation in graphical models with loops","volume":"12","author":"Weiss","year":"2000","journal-title":"Neural Comput."}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370203001103?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370203001103?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T05:48:12Z","timestamp":1734068892000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0004370203001103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2003,12]]}},"alternative-id":["S0004370203001103"],"URL":"https:\/\/doi.org\/10.1016\/s0004-3702(03)00110-3","relation":{},"ISSN":["0004-3702"],"issn-type":[{"type":"print","value":"0004-3702"}],"subject":[],"published":{"date-parts":[[2003,12]]}}}