New answers tagged spanning-trees
0
Just to make it clear, the problem of finding a spanning tree with a maximum number of leaves is NP-hard. There's a simple 2-approximation algorithm due to Solis-Oba [1] which looks implementable with reasonable effort. In fact, I don't think anything better is known. There are other algorithmic approaches as well (e.g., FPT algorithms), but I'm not sure if ...
Top 50 recent answers are included
