99-24: Sequential Testing of Series-Parallel Systems of Small Depth

DIMACS TR: 99-24

Sequential Testing of Series-Parallel Systems of Small Depth

Authors: Endre Boros and Tonguc Unluyurt

ABSTRACT
We consider the problem of testing sequentially the components of a multi component system, when the testing of each component is costly. We consider a polynomial time testing policy for series-parallel systems, proposed in the literature. Generalizing published results, we prove that the considered policy is cost-minimal in the average case sense, for two sub-families of series-parallel systems. We also demonstrate via examples that neither this algorithm nor some of its improved versions are optimal for general series-parallel systems, disproving some published claims.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-24.ps.gz

DIMACS Home Page