DIMACS TR: 99-24
Sequential Testing of Series-Parallel Systems of Small Depth
Authors: Endre Boros and Tonguc Unluyurt
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:
DIMACS Home Page