Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


k minimum spanning trees


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
No replies to this topic

#1 oggs91   Members   -  Reputation: 281

Like
0Likes
Like

Posted 06 June 2012 - 10:40 AM

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

Sponsor:



Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS