wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> NEW PROBLEM: MORE SPANNING TREES
        
(Message started by: Pietro K.C. on Sep 24^th, 2002, 1:28pm)

Title: NEW PROBLEM: MORE SPANNING TREES
Post by Pietro K.C. on Sep 24^th, 2002, 1:28pm

Let G = (V, E) be an undirected grap, and consider the problem of finding out whether G has a spanning tree where every vertex has degree less than or equal to k.

Show that P is NP-complete.

Note: the degree referred to is the degree a vertex has in the spanning tree, not in the whole graph, because then all degrees would be predetermined, and P would be no fun at all. :) For example, consider a triangle ABC, where sides are edges and vertices are - well, vertices. Then all nodes have degree two. However, in the spanning tree {(A,B),(B,C)}, A and C have degree 1.