1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?