My Math Forum

My Math Forum (
-   Applied Math (
-   -   Advanced Math: Algorithm to Solve an Optimal Set (

forkconfig February 6th, 2014 07:38 AM

Advanced Math: Algorithm to Solve an Optimal Set
I want to develop a program which analyzes sets. I think the best way I can describe the program is using an example. For those of you familiar with toggle coverage that is the purpose of this application.

The goal is to reach 100% coverage. TestA stresses X% of the chip, but % doesn't matter, what matters is which set of pins/portions of the chip is stressed. So let us say TestA stresses setA and TestB stresses setB, so on and so forth for Y number of tests until we reach 100% coverage.

Here is the problem, we want to reduce Y to Y' such that Y' is the minimum ammount of tests required. How? Lets say TestA can be eliminated because by running TestB, C, D we obtain the set which TestA would have covered.

The question I have is, I want to do research on this area (IEEE articles and so on) but don't know what to search? I am looking for titles, papers, etc. to help me determine an algorithm. If you have 1000 tests, I don't want to say "Can I eliminate testA with B? no? What about B+C? no? What about B+C+D?" In addition to being very slow, it doesn't account for the fact that sure A might be replaced by B+C+D, but A would have significantly helped with removing D+E+F.

I'd appreciate help in going in the right direction.


JC February 6th, 2014 02:25 PM

Re: Advanced Math: Algorithm to Solve an Optimal Set
I think your problem is equivalent to minimum set cover problem. Check it out! Unfortunately efficient algorithm to solve this problem is not known, however if the task is not too big it can be solved by simple bruteforce (and using some tricks like pruning to speed up the search).


Originally Posted by forkconfig
The question I have is... ...helped with removing D+E+F.

The last indent is a bit unclear to me, though.

All times are GMT -8. The time now is 05:04 AM.

Copyright © 2019 My Math Forum. All rights reserved.