Spanning tree modification - Programmers Heaven

Howdy, Stranger!

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


Spanning tree modification

finfin Posts: 1Member
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.