in the number of leaves but only polynomial in the input graph size. The klam value of these algorithms (intuitively, a number of leaves up to which the problem can be solved within a reasonable amount of time) has gradually increased, as algorithms for the problem have improved, to approximately 37, and it has been suggested that at least 50 should be achievable.

In graphs of maximum degree three, the connected dominating set and its complementary