• 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.


2. Homework Equations



3. The Attempt at a Solution
 

Answers and Replies

berkeman
Mentor
56,132
6,164
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
903
Replies
2
Views
877
Replies
4
Views
2K
Replies
15
Views
2K
  • Last Post
Replies
7
Views
2K
Top