My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
February 6th, 2014, 07:38 AM   #1
Joined: Feb 2014

Posts: 1
Thanks: 0

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.

forkconfig is offline  
February 6th, 2014, 02:25 PM   #2
Joined: Jun 2008

Posts: 45
Thanks: 0

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.
JC is offline  

  My Math Forum > College Math Forum > Applied Math

advanced, algorithm, math, optimal, set, solve

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Translating Algorithm into Math? flyjoe Real Analysis 0 February 12th, 2013 05:17 PM
Math algorithm najken Computer Science 3 September 1st, 2012 02:30 PM
Help !.. need advanced math formula put into excell ! TheSwede Advanced Statistics 102 September 19th, 2011 01:48 AM
Advanced Algebra...well advanced for me =p peterle1 Algebra 5 November 23rd, 2009 09:17 AM
Solve for 'x' algebraically, extremely difficult (advanced)? IsenseHelp Algebra 2 January 11th, 2009 04:10 PM

Copyright © 2019 My Math Forum. All rights reserved.