You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

A probabilistic search algorithm for finding suboptimal branchings in mutually exclusive hypothesis graph

Article type: Other

Authors: Davydov, M.V.

Affiliations: L'viv Polytechnic National University, 12 Bandery Street, L'viv, Ukraine. E-mail: [email protected]

Keywords: Mutually exclusive hypothesis graph, Edmonds'algorithm, suboptimal branching

DOI: 10.3233/KES-140302

Journal: International Journal of Knowledge-based and Intelligent Engineering Systems, vol. 18, no. 4, pp. 247-253, 2014

Published: 12 November 2014
Get PDF

Abstract

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.

Show more