Find the minimum spanning tree. Find the nodes with indegree of 1 and mark the node which connects to that node with indgree 1.
On Wed, Oct 7, 2009 at 11:08 PM, Ramaswamy R <ramaswam...@gmail.com> wrote: > We have to find the minimum cardinality out of all possible bi-partite sets > of the graph. (provided the graph is 2 colourable.) > Brute force method would be to choose N nodes from V and check for its > connectivity with the rest. First we'd have vC1 sets, then vC2 and so on. > > Am unaware of a better algorithm. > > On Wed, Oct 7, 2009 at 1:07 AM, ankur aggarwal > <ankur.mast....@gmail.com>wrote: > >> Given a graph.. >> >> Find the minimum number of coloring (Marking) required to node such that >> every node in the final graph is connected by at least one of the >> colored(marked) node. >> >> ex: >> AB >> AC >> BD >> BE >> CF >> >> sol: 2 nodes to be colored. >> >> i.e. Colouring C and B would suffice.. >> >> >> > > > -- > Yesterday is History. > Tomorrow is a Mystery. > Today is a Gift! That is why it is called the Present :). > > http://sites.google.com/site/ramaswamyr > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
