• Advertisement
Sign in to follow this  

k minimum spanning trees

This topic is 2084 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

this is for a small project at university:

we have to implement a java algorithm which produces a k-minimum spanning tree on a given graph (a minimum spanning tree with k nodes)
further we have to solve this with an algorithm based on branch and bound

my problem is to get useful heuristics for upper and lower bounds, to eliminate soon a lot of problems

my current approch works as following:
lower bound:
weight of currently fixed #e edges in graph + one adjacent edge to them + the weights of the k-1-e smallest edges

upper bound:
currently only set if a valid solution was found

Share this post


Link to post
Share on other sites
Advertisement
Sign in to follow this  

  • Advertisement