Spanning tree modification

Hail to you my fellow geeks
I would like to find a polynomial algorithm for the following problem for my project:
Suppose you have a graph (normal, not directed). You want to find a spanning tree (any, doesnt have to be minimum), but it has to respect one rule: the edges are separated into n groups and each of these groups has a positive integer X assigned to it meaning "from this group, no more than X edges can be used in the spanning tree".
Can this be done in polynomial time? Any hints will be greatly appreciated, thanks.
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories