Experimental results on preprocessing of path/cut terms in sum of disjoint products technique

Abstract

Experimental results are presented showing the number of disjoint products and computer time involved in generating sum of disjoint product (SDP) terms. To help obtain the results, the authors have considered 19 benchmark networks containing paths (cuts) varying from 4 (4) to 780 (7376). Several SDP techniques are reviewed and are generalized into three propositions to find their inherent merits and demerits. An efficient SDP technique is, then, utilized to run input files of paths/cuts preprocessed using (1) cardinality, (2) lexicographic, and (3) Hamming distance ordering methods and their combinations. The experimental evaluation has been performed on an FPS 500 system. Results are analyzed, and it is shown that the preprocessing based on cardinality or its combinations with (2) and/or (3) performs better.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>