The problem seems to be minimum dominating set problem (which is NP-complete i think). But since the number of nodes will be <=26, it can be solved by some intelligent brute force.
Something like this might work: Take all subsets of the given nodes. Iteratively keep increasing the size of the subsets. i.e., take all 1-size subsets of nodes .. then take all subsets of size 2, then 3 and so on ... Now see if the current subset of the given node set forms the dominating set. If yes then problem is solved and the solution can be printed. On Wed, Jul 1, 2009 at 9:24 PM, Dave <[email protected]> wrote: > > This can be formulated as a 0-1 integer programming problem. > > Define the matrix A such that a(i,j) = 1 if machine i is connected to > machine j, and = 0 otherwise (with the interpretation that every > machine is connected to itself). > > Let x be a vector whose elements are in the set {0, 1}, where x(j) = 0 > means that machine j is not an administrative machine and x(j) = 1 > means that it is. > > Then the 0-1 integer programming problem is: > > detemine x to > minimize sum{ x(i) } > subject to [A*x](i) >= 1. > > The inequality above means that the i'th component of the matrix- > vector product A*x is >= 1. It simply means that machine i is > connected to at least one administrative machine. > > You should be able to find software or algorithms to solve 0-1 integer > programming problems. > > Dave > > On Jul 1, 7:47 am, priya k <[email protected]> wrote: > > we have many machines connected to each other. However, administering > these > > machines is a great hassle. That is because a machine can be administered > > only by a machine connected directly to it (a machine that is an > > administrator can administrator itself). So, the system administrators > have > > decided to convert some of the machines in the network to "administrative > > machines". However, the cost of converting a machine to an administrative > > machine is $100, which is pretty high. So, the system administrators > > approach you to help them out. > > > > You will be given a list of machines which have a direct connection > between > > them. You need to compute the least cost that the company needs to incur > so > > that every machine in the final network is administrable by at least one > of > > the machines converted to administrative machines. > > > > You are given as input the node pairs which are connected to each other. > You > > are supposed to find the least amount of money in dollars that you need > to > > spend so that every machine in the network is administered by at least > one > > administrator machine. > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
