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!


Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

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.