Найти все поддеревья размера N в неориентированном графе

Учитывая неориентированный граф, я хочу сгенерировать все подграфы, которые являются деревьями размера N, где размер относится к количеству ребер в дереве.

Я знаю, что их много (экспоненциально много, по крайней мере, для графов с постоянной связностью) - но это нормально, поскольку я считаю, что количество узлов и ребер делает это управляемым, по крайней мере, для небольших значений из N (скажем, 10 или меньше).

Алгоритм должен быть эффективным с точки зрения памяти, то есть не должен иметь в памяти сразу все графы или какое-то их большое подмножество, так как это, вероятно, превысит доступное память даже для сравнительно небольших графов, так что желательно что-то вроде DFS.

Вот что я думаю в псевдокоде, учитывая начальный граф граф и желаемую длину N :

Выберите любой произвольный узел, корень в качестве отправной точки и вызовет alltrees (graph, N, root)

alltrees(graph, N, root)
 given that node root has degree M, find all M-tuples with integer, non-negative values whose values sum to N (for example, for 3 children and N=2, you have (0,0,2), (0,2,0), (2,0,0), (0,1,1), (1,0,1), (1,1,0), I think)
 for each tuple (X1, X2, ... XM) above
   create a subgraph "current" initially empty
   for each integer Xi in X1...XM (the current tuple)
    if Xi is nonzero
     add edge i incident on root to the current tree
     add alltrees(graph with root removed, N-1, node adjacent to root along edge i)
   add the current tree to the set of all trees
 return the set of all trees

. Это найдет только деревья, содержащие выбранный начальный корень, поэтому теперь удалите этот узел и вызовите все деревья (граф с удаленным корнем, N, новое произвольно выбранный корень) и повторять до тех пор, пока размер оставшегося графа не будет

Я также забыл, что каждый посещаемый узел (каждый корень для некоторого вызова всех деревьев) должен быть помечен, а набор дочерних элементов, рассмотренный выше, должен быть только смежными немаркированными дочерними элементами. Я предполагаю, что нам нужно учитывать случай, когда нет неотмеченных дочерних элементов, но глубина> 0, это означает, что эта «ветвь» не смогла достичь требуемой глубины и не может быть частью набора решений (поэтому весь внутренний цикл, связанный с этот кортеж можно прервать).

Так это сработает? Какие-нибудь серьезные недостатки? Есть ли более простой / известный / канонический способ сделать это?

Одна из проблем описанного выше алгоритма заключается в том, что он не удовлетворяет требованию эффективного использования памяти, поскольку рекурсия будет содержать в памяти большие наборы деревьев.