1
$\begingroup$

Given a graph $G$ with $n$ nodes, is there an algorithm to find $m$ subtrees, each with $\lfloor n/m\rfloor$ or $\lceil n/m\rceil$ nodes, such that every node of $G$ is in exactly one tree?

Other than brute forcing the problem, it there an algorithm that can create the partitions of a graph that satisfy these conditions?

Furthermore, is there a way to enumerate all such possible partitions that lead to a set of subtrees?

Note I am not looking to prove existence. I actually want to use such an algorithm, so I am really looking for its description.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Are you sure you want to enumerate all partitions? It seems likely that there could be exponentially many such partitions, so any algorithm to enumerate all partitions would necessarily take at least exponential time. What do you want the algorithm to do in that case? $\endgroup$ – D.W.♦ Dec 26 '14 at 19:47
  • $\begingroup$ @D.W. I want the option, such that I can enumerate say, 1000 legal partitions (or ever better, allow me to sample 1000 random partitions from the space) $\endgroup$ – soandos Dec 26 '14 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.