Solving Connected Graphs with Algorithm: K Blue/Red Edges

  • Thread starter Thread starter frank_buf@yahoo
  • Start date Start date
  • Tags Tags
    Algorithm Hi
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
1 reply · 3K views
frank_buf@yahoo
Messages
1
Reaction score
0

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

 
Physics news on Phys.org
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?