Wikipedia

Degree-constrained spanning tree: Difference between revisions

Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Citation bot (talk | contribs)
Bots
5,866,819 edits
m Alter: title, isbn. Add: citeseerx, title-link. | You can use this bot yourself. Report bugs here. | User-activated.
→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
Line 19:
==Approximation Algorithm==
 
{{harvtxt|Fürer|Raghavachari|1994}} gavegive an approximationiterative algorithmpolynomial fortime the problemalgorithm which, ongiven anya givengraph instance<math>G</math>, eitherreturns showsa thatspanning thetree instancewith hasmaximum degree no treelarger ofthan <math>\Delta^* + 1</math>, where <math>\Delta^*</math> is the minimum possible maximum degree over all spanning trees. Thus, if <math>k or= it\Delta^*</math>, findssuch andan returnsalgorithm will either return a spanning tree of maximum degree <math>k</math> or <math>k+1</math>.
 
==References==
Retrieved from "https://en.wikipedia.org/wiki/Degree-constrained_spanning_tree"