Hi need help with algorithm

  • #1

Homework Statement



Given a connected graph G = (V,E). Let n = |V |. Each edge in G is already colored
with either RED or BLUE. Devise an efficient (i.e. polynomial-time) algorithm which, given an integer k,
1 <= k <= n − 1, either (a) returns a spanning tree with k BLUE edges and n − 1 − k RED edges, or (b)
reports correctly that no such tree exists.


Homework Equations





The Attempt at a Solution

 

Answers and Replies

  • #2
berkeman
Mentor
58,752
8,869
Welcome to the PF, Frank. You need to show us all of your work and thoughts on this problem before we can help you. Why did you not fill in #2 and #2 in our Homework Posting Template? What are the relevant concepts that we should use in trying to help you figure out how to solve this question?
 

Related Threads on Hi need help with algorithm

Replies
0
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
971
Replies
2
Views
957
Replies
4
Views
2K
Replies
17
Views
3K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
2
Views
1K
Top