Open AccessA probabilistic search algorithm for finding suboptimal branchings in mutually exclusive hypothesis graph
Author(s) -
Maksym Davydov
Publication year - 2014
Publication title -
international journal of knowledge-based and intelligent engineering systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 20
eISSN - 1875-8827
pISSN - 1327-2314
DOI - 10.3233/kes-140302
Subject(s) - probabilistic logic , probabilistic analysis of algorithms , algorithm , computer science , graph , mathematics , theoretical computer science , artificial intelligence
The concept of mutually exclusive hypothesis graph (MEHG) is introduced and NP-completeness of several problems on MEHG is proved. A probabilistic search algorithm is proposed for finding suboptimal branchings in such graphs and its performance is evaluated for graphs with uniform and exponential weight distribution.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom