Diagnosing Tree-Decomposable CurcuitsYousri El Fattah (email@example.com) & Rina Dechter (firstname.lastname@example.org)
This paper describes a diagnosis algorithm called structure-based abduction (SAB) which was developed in the framework of costraint networks . The algorithm exploits the structure of the constraint network and is most efficient for near-tree problem domains. By analyzing the structure of the problem domain, the performance of such algorithms can be bounded in advance. We present empirical results comparing SAB with two model-based algorithms, MBD1 and MBD2, for the task of finding one or all minimal-cardinality diagnosis. MBD1 uses the same computing strategy as algorithm GDE . MBD2 adopts a breadth-first search strategy similar to the algorithm DIAGNOSE . The main conclusion is that for nearly acyclic circuits, such as the N-bit adder, the performance of SAB being linear provides definite advantages as the size of the circuit increases.