6 Replies - 7938 Views - Last Post: 19 April 2013 - 04:40 PM

#1 viktor.slavkovic  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 20
  • Joined: 27-June 12

minimal cost spanning tree with exactly K white edges

Posted 18 April 2013 - 03:52 PM

Let's say:

  • G is an undirected connected graph
  • G has M edges
  • Every edge has it's weight/cost
  • Every edge has it's color - black or white


How should I find Minimal Cost Spanning Tree with exactly K white edges? What would the complexity be?

Thanks in advance.

This post has been edited by viktor.slavkovic: 18 April 2013 - 03:53 PM

Is This A Good Question/Topic? 0
  • +

Replies To: minimal cost spanning tree with exactly K white edges

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3590
  • View blog
  • Posts: 11,166
  • Joined: 05-May 12

Re: minimal cost spanning tree with exactly K white edges

Posted 18 April 2013 - 09:21 PM

What have you tried so far?
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10596
  • View blog
  • Posts: 39,259
  • Joined: 27-December 08

Re: minimal cost spanning tree with exactly K white edges

Posted 18 April 2013 - 09:31 PM

I would adapt Kruskal's algorithm here since it gives you more global control over the edges than say Prim's algorithm.
Was This Post Helpful? 0
  • +
  • -

#4 viktor.slavkovic  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 20
  • Joined: 27-June 12

Re: minimal cost spanning tree with exactly K white edges

Posted 19 April 2013 - 08:35 AM

I've tried Kruskal. And then if I used less then K white edges, I discard minimal black edge, or else discard minimal white edge. I repeated this until I've got exactly K edges. It's certainly slow.

View Postmacosxnerd101, on 18 April 2013 - 09:31 PM, said:

I would adapt Kruskal's algorithm here since it gives you more global control over the edges than say Prim's algorithm.


How would you adapt Kruskal?
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10596
  • View blog
  • Posts: 39,259
  • Joined: 27-December 08

Re: minimal cost spanning tree with exactly K white edges

Posted 19 April 2013 - 08:46 AM

Edges are incident to two vertices. I'd start by trying to maximize the number of vertices in your spanning forest. If a vertex only has white edges, I'd start with it. Then move onto the vertices with edges of both colors.
Was This Post Helpful? 1
  • +
  • -

#6 viktor.slavkovic  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 20
  • Joined: 27-June 12

Re: minimal cost spanning tree with exactly K white edges

Posted 19 April 2013 - 04:27 PM

View Postmacosxnerd101, on 19 April 2013 - 08:46 AM, said:

Edges are incident to two vertices. I'd start by trying to maximize the number of vertices in your spanning forest. If a vertex only has white edges, I'd start with it. Then move onto the vertices with edges of both colors.

Thank you a lot. It seems to be a good idea. I'll give it a try...
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10596
  • View blog
  • Posts: 39,259
  • Joined: 27-December 08

Re: minimal cost spanning tree with exactly K white edges

Posted 19 April 2013 - 04:40 PM

Glad to help! Good luck! :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1