Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hi need help with algorithm

  1. Feb 11, 2007 #1
    1. The problem statement, all variables and given/known data

    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. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Feb 11, 2007 #2


    User Avatar

    Staff: Mentor

    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook