• Support PF! Buy your school textbooks, materials and every day products Here!

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
56,439
6,357
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 for: Hi need help with algorithm

Replies
0
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
912
Replies
2
Views
884
Replies
4
Views
2K
Replies
15
Views
3K
  • Last Post
Replies
7
Views
2K
Top