# minimal cost spanning tree with exactly K white edges

Page 1 of 1

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

### #1 viktor.slavkovic

Reputation: 2
• 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?

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

• Code herder

Reputation: 4255
• Posts: 13,613
• 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?

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11391
• Posts: 42,928
• 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.

### #4 viktor.slavkovic

Reputation: 2
• 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.

macosxnerd101, 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.

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11391
• Posts: 42,928
• 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.

### #6 viktor.slavkovic

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

## Re: minimal cost spanning tree with exactly K white edges

Posted 19 April 2013 - 04:27 PM

macosxnerd101, 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...

### #7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11391
• Posts: 42,928
• Joined: 27-December 08

## Re: minimal cost spanning tree with exactly K white edges

Posted 19 April 2013 - 04:40 PM