Re: modified-- strongly connected components(SCC)?

Amit Gupta wrote: 
Hi,

I have a variation of SCC problem to solve. In a directed graph G(V,E),
the virtex set has an object-type associated with it. The graph can
contain any
number of virtices with different object-types. The algorithm in Cormen
book provides a polynomial time algorithm for finding all SCCs.

The variation I have is, given a directed-graph where each virtex has
an
object-type parameter, find all the strongly connected component, with
the restriction that each component can contain no more than "M"
virtices of a given type. I dont want to first find all SCC
(disregarding the object-type of the virtex) and then prune the
components which have more than M virtices of a given type. Is there a
way, the algorithm can be modified to generate the components with this
restriction.

Probably, what can make the problem easier is that the restriction is
only on a single virtex-type, i.e find SCCs such that virtex with
object type "K" occurs no  more than M times.

Thanks,
Amit


PS: I am not sure, if this is the right forum for the question (the
question is about algorithms)however, I could not find any other
*active* forum to post this question.


I have a question about the problem definition. Suppose the graph
contains an SCC with 2M vertices of the specific type. Do you want to
report two components, each with M vertices, or one component and ignore
the remaining vertices in the same SCC?

Patricia
.