Content deleted Content added
Scrabbler94 (talk | contribs) →Approximation Algorithm: original description not quite right, as k is given as input. If k = \Delta^*, where \Delta^* is the minimum max degree over all spanning trees, then it is correct |
No edit summary Tags: Mobile edit Mobile app edit iOS app edit |
||
Line 3:
==Formal definition==
Input: ''n''-node undirected graph G(V,E); positive [[integer]] ''k'' ≤ ''n - 1''.
Question: Does G have a spanning tree in which no [[Node (computer science)|node]] has degree greater than ''k''?
| |||